In addition to CheckTx, we should also have a "Recheck Tx". The functionality would basically be the same, but it would be intended for use on things that have already passed a CheckTx once before. The reason for this is that the app could then skip certain checks, such as signature verification. Regardless of state changes, for most txs the signatures will remain valid. If there was a "MsgChangePubkey" this could be checked in the application logic, and in that case assoc. signature re-checked. (Given that this doesn't yet exist, doesn't seem like a concern right now)

Then we would call recheck in the mempool instead of check.

Right now rechecking every tx on each new block, and therefore doing each signature verification is going to be a significant hit on performance if you have a non-trivially filled mempool. Recall that our current Secp signature verification implementation is 505039 ns/op. Right now the bitcoin mempool is at 15MB. (https://www.blockchain.com/charts/mempool-size). The average bitcoin tx is ~300 bytes, which means that there are 52428 txs in the mempool. At signature verification time we have, this means a recheck would take 26 seconds. Thus the proposed scheme seems to me be a very important concern, as the mempool rechecking processing time between blocks would be 26 seconds. (Perhaps divided by a small constant factor due to parallelization)