The database is going to be your best bet.
Way too expensive. I reckon my original plan might be the cheapest option yet, even if convoluted.
Also, you might want to consider using the cold wallet to protect the hot wallet, not to protect individual accounts.
I may be missing what you intended to say, but the cold wallet is used to protect the hot wallet, which happens to have several accounts. Note that these accounts are not associated with external users; they all belong to me, and are just separate for administrative/accounting purposes.
I can't imagine any possible database where a single query is going to be more expensive than a RPC call to bitcoind.
Change your administrative plan.
What you are trying to do isn't worth it. Set your policies based on the wallets, not the accounts.