If you have a backup you should be able to restore from that whether it is done by Time Machine or one of the other programs mentioned. Without a backup any e-mail not stored on the providers server would be lost. Of the hard drive were to remain intact the e-mail could be restored from there although removing the drive to place in an enclosure can be interesting in some models.
Hi Ron - you might want to tell us 'what' kind of email accounts your have? There are two main ones for incoming mail: POP3 or IMAP - POP3 is like the mailman, i.e. once the mail is delivered to your mailbox (think computer HD), then that's the only copy and backup is important; OTOH, in IMAP, the mail is kept on the server of the mail client you are using so deletion can occur at various levels - you need to understand the difference.
As an example, I used mainly Yahoo Mail - below is a screen capture of Apple Mail opened to my account; all of the folders on the left are on the Yahoo servers - now I can delete information in these folders from my computer @ home or using Yahoo Mail via a browser but if my computer went down and my mail was still w/ Yahoo, I should be able to retrieve it - SO, we need to know how your mail is setup.