A long shot, but you don't happen to use IMAP by any chance do you? Our IMAP server stores every email as a separate file so it would be a case of recovering the deleted folder on the server in my case.

If you're just a home user using POP3, you're stuffed but I think you already realise that...