Here is a program that will cost after the trial period. I do not know if it actually works. One thing I do know, use your computer as liitle as possible until the mail is found. They are on your hard drive just invisible. Every use, they will become overwritten making it more and more difficult to restore.
Of course go to the website of your email provider to insure that they are not still on the server. Recovery for Windows Mail - Recover Deleted Email Messages in Vista Windows Mail.
You can, also thry this free applications which works very well with files, but dont know about email DiskDigger | The trusted data recovery solution
Final attempt would be to try a system image.