To add to this thread, Outlook Web Access or Web mail has a feature that stores most recently deleted items on your Exchange Server. this feature does vary from hosted providers.

If you are using a full version of the OWA for exchange 2007 or 2010 and not a lite version, Select options the Deleted options. There should be a field with delted items that have been removed from your client or web mail client. you can use this to restore messages accidentally removed.

Normally this feature is present in the IE8 browser.

Hope this helps.