If HD wallets just use an incrementing integer added to the seed to generate keys, I figure it would be easy. Just always send all change to a new address, increment the counter, and disgard the old address. That way all you have to keep a record of is the seed and the current counter. The last option to add would be to scan all addresses, from first to the counter, to see if they have any coins, and sweep the coins to the most recent address, in case one of your old addressees get paid.
As for restoring backups, just have it scan addresses one by one until it finds one with a balance.
Implementing BIP 32 and creating keys is the easy part. Where it really starts getting tricky is when have to track track the unspent outputs and transaction history of an ever increasing key set. Some have suggested a moving window of keys to track, and that will work as long as no one sends funds to an address outside the window. Bitsofproof is working on such a solution, and it is going to be interesting to see how it works out. My guess is that a lot of confusion will arise when funds seemingly disappear when they are received outside the window...As for restoring backups, just have it scan addresses one by one until it finds one with a balance.
You can amended this by doing a complete scan once in a while. This however is where it gets really expensive. If you have your own dedicated powerful host running Armory this is not a problem, but I don't think it scales to thousands of wallets.
