If these messages were downloaded via the POP3 protocol (like Hotmail, Gmail or the like), you’re S-O-L. Sorry. However, if you are pointing to a corporate Exchange server, browse to the Deleted Items folder, then from the Action menu, select “Recover Deleted Items”. Depending on how long it’s been since you deleted the items and what your administrator has the retention set to, you may have access to these items. Good luck!