When using Outlook and you have deleted a message, then the Exchange-server will by default retain deleted items, so they are recoverable 7 days. To recover a mail select the "Deleted Items"-folder go to Tools, Recover Deleted Items.

If doing a hard delete by holding down Shift+Delete to delete a message, then it is not moved to "Deleted Items"-folder. Making it impossible to recover such a deleted message the standard way. Instead one can apply the following registry key to enable recovery of messages from any folder:

[HKEY_LOCAL_MACHINE \SOFTWARE \Microsoft \Exchange \Client \Options]
DumpsterAlwaysOn = 1

More info MS KB178630
More info MS KB246153

Credits winnetmag.com