Strictly speaking, finding the most efficient way to structure storage is NP-class task meaning that it will require too much resources given the amount of bits.
Dictionaries are binary trees (up to 2 branches in cell), though reading and updating them is actually cheaper than quadro-trees. So I'd recommend using dicts.
Yes, the owner will eventually lose all the money.
However, data stored by wallet (let's assume v3r2) is less than 1 KiB, so to lose even 1 TON you'll have to wait thousands of years, over which time the network will clearly have some other breaking changes.
It should be possible to cut off the last half of key (64 HEX characters), which is actually public key, and use the rest in other wallets.
In testnet environment, there is opcode GASCONSUMED, doing exactly that. The update isn't shipped in mainnet yet.