There are several 4xx codes that would fit (beginning with the good old 404) but in any case a 5xx isn't appropriate here, in my opinion.
No, 404 is appropriate if the transaction isn't found, as in it does not exist in the blockchain.
422 means "I understand your request, it is legal, but I can not process it for whatever reason".
500 is definitely wrong though, there is no internal error happening, as in "unexpected error".