Couple of things.
1. Root your phone, then use Titanium to do full backups. You can then copy these periodically to your PC.
2. Root your phone, then make complete backups via Clockwork, again saving them to your PC periodically.
3. Dont loose the phone (sorry couldnt resist!)
As someone who has lost an android phone before, I feel your pain.
Thankfully, I got in the habit of doing the above 2 steps (titanium backup 3 times a week, and Rom backup monthly, then archive to PC after the ROM backup).
Saved my butt the second time it happened....though the loss of a 32gig micro sd was ultimately the tougher loss!!!!