From my understanding, you have to recheck most of the blockchain just to see if people have sent money to you. Outgoing transactions would just be remembered on device right? So how can wallets like Coinomi be so fast?
As Flux alluded to, most wallets nowadays don't compute their own balances, they query an API service. Behind this API service is a "full node" of the cryptocurrency they need info on. By maintaining a full node, the service has the balances of every address on the blockchain on-hand to be able to serve up via the API.
Additionally, some blockchains support "light clients", which allow a wallet to query the network directly without downloading and maintaining the entire blockchain. In this case, an API may not even strictly needed.
As a side note, a wallet never needs to "recheck most of the blockchain" to see if it has received money. Even if your wallet is doing all the work itself without any API service, it only needs to check the new stuff that happened since you were last logged in and synced up with the network.
There are a few different ways that cold wallets can be fast. Coinomi, for example, uses a technique called "headers-first synchronization." This means that the wallet only downloads the headers of the Bitcoin blockchain, which are the cryptographic proofs that link together all of the blocks. It then verifies those headers by checking them against the Bitcoin network.
Once it has verified a certain number of headers, it will download the corresponding blocks and then continue to synchronize with the network. This technique allows Coinomi to be much faster than other wallets since it doesn't have to download the entire blockchain.
Other wallets may use different synchronization techniques, or they may cache the results of previous transactions, which allows them to be faster than a wallet that has to download the entire blockchain every time.