By the sounds of things a complete restore to your last backup may be in order as it sounds like multiple files have been damaged or removed.
Could you boot from the Leopard install disc by booting the machine with the C key held down and instead of running the install process, go to Utilities, Restore System from Backup. Then select your backup source (your external Time Machine drive), choose which backup you want to restore (the most recent), then pick the destination drive and follow the steps to restore.
Once it is done your computer should be back to the correct state.
Let us know if you have any issues or if you just wish to try a single file restore.
So how many backups do you have?
When you restore from a Time machine drive it should restore everything, OS and all.
If this is not the case then it sounds like your Bakups are either incomplete or damaged.
If that is the case then you may try individual file restores using Time Machine.
To restore a particular file, first use Spotlight to specify the file or folder location you need to recover. For example, if you need to recover a presentation on architecture, search for "architecture" using Spotlight.
Once you've located the file you want to restore, (or a file you want to restore even if Spotlight can't find it), click the Time Machine icon in the Dock. Spotlight will pass your search to Time Machine.
In the Time Machine "time travel" window, use the large arrows to the right of the search window, or the timeline on the right window edge of Time Machine, to browse through your backups. Your previous search is performed in every backup window as it is displayed.
When you've found the file you want, select it and use Quick Look to make sure.
Click Restore to restore the file. The restored item is returned to its original location. For example, if the file was in the Documents folder, it is returned to the Documents folder.
Time Machine may ask if you want to re-create one or more folders in order to return a restored item to its original location so say yes and follow the prompts.
Let me know what happens.
Sorry to hear that you could not even get your mail back.
For a backup solution you may wish to consider somethig like a Maxtor One touch http://www.maxtorsolutions.com/en/catalog/OTIII_Turbo/
The link I provided is for the one I use however you can use a smaller unit which is a lot cheaper.
With something like the onetouch if you have a disaster you can boot the machine directly from the external drive or you can just direct transfer the entire disk image back to your computer, It also has both automated backup software and a One Touch button on the front that you hit if you want to run a backup
Once again I am sorry I was unable to help you recover your data.