Wallets would have to keep track of their own adresses, if they already used them and what they already used them for.
Another solution is to switch seeds after every snapshot and just send all your IOTA to the first address of the new seed.
What would work as well is to ask a Permanode (node that doesn‘t do snapshots but saves the whole Tangle history) about which addresses were already used. Of course you‘d have to trust the node to not lie to you, wait for you using the address and stealing your IOTAs.
I think local storage is the optimal solution for most cases. Of course the other ones will most likely have some use cases as well.