For those of you who admin Exchange environments and have Deleted Item retention enabled on the server (a smart admin would, less need to restore from tape due to user stupidity of deleting important emails), MS Outlook only allows recovery from the "Deleted Items" bin by default.
If you also purge your users folders like I do regularly (Deleted Items and Sent Items) so they dont save years of email and for the people who forget to empty the Deleted Items bin, if the Mailbox Cleanup removes messages from any folder other than the Deleted Items, the user cant get them back if they need it. Same thing goes if they "Shift + Delete" a message from any other folder in the mailbox. However, adjusting a small Reg key on the client allows the "Recover Deleted Items" menu item to work on any folder in the users mailbox:
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Exchange\Client\Options]
"Dumpsteralwayson"=dword:00000001
Makes life as an Exchange Admin a little easier so the users can recover their own items without bugging you, leaving you to the never ending task of keeping Exchange stable and running

This hack works with machines running MS Outlook 2000 and up.