To enable the Recover Deleted Items option in the Outlook|Tools menu, and just to clarify, this is for Exchange users.

Close Outlook
Start regedit
Navigate to: HKEY_LOCAL_MACHINE\Software\Microsoft\Exchange\Client\Options
Create a new|DWORD Value with the name DumpsterAlwaysOn and set its value to 1
Then restart Outlook and go to Tools|Recover Deleted Items