This would also explain why it's slowly getting slower. The update search across a growing utxo table is getting linearly longer and longer... I'm up to 700m utxos
Thinking out loud here: maybe you can have a look at how Bitcoin Core handles this? For each block, it checks all UTXOs in the
chainstate directory, and especially if it can cache everything it's fast.