It depends on the type of mail account you have.
If you have an Exchange account (Microsoft Exchange, the Microsoft mail
server used in many busines environments), open your Deleted Items folder
and
click on Tools > Recover Deleted Items. Emails that are recovered are
returned to the Deleted Items folder. What you can recover depends on what
your Exchange Admin has chosen to set Deleted Item Retention for. I think
the
default is 7 but most of us change that to be longer so we don't have to
recover mailboxes.
If you have a POP3 account with a PST file, try the following:
http://www.howto-outlook.com/howto/restoredeleteditemsfromanoutlookpst.htm
Good luck, let me know how you make out.