Ever heard of doing off-site backups?
It's not a backup script.
How were you able to run out of key-pool with so many "recent backups"?
Something just doesn't add up here.
As I mentioned, this occurred after the release of 0.5.0. The first time that version runs it rewrites your wallet, which entails creating a new key pool. If I had realized this at the time, I would not have deleted wallet.dat and would not have had this problem. Since I didn't, though, I deleted it and lost the completely new pool, from which the ~77 BTC change address pulled.