At one of my clients, we limit their users mailboxes to keep the Exchange server humming along. We use an archiving program to keep older mail around in accordance with our document retention policies.
One of the things we mandate is that Outlook purges its Deleted Items folder upon closing. We've had users maintain 3800 (unread!) messages in their deleted items folder and then complain loudly when they run out of mailbox space citing that they might need something in their Deleted Items folder. (Of course, this runs counter to the design of the Deleted Items folder is -- short term storage for items no longer needed. Long term storage should be used in either the users' folder or the server's file system.)
These complaints have subsided now that everyone has had a chance to live with the policy... but there are still some times when people delete something, close Outlook and then realize they can't get it back.
(Let's assume the archiver is off-line.)
Outlook Web Access can come to the rescue and recover some of the lost items as long as it was deleted recently. Stuff deleted a year ago is long gone.
Log in to Outlook Web Access. (This works in Outlook Web Access 2000 and 2003. Screenshots are from OWA 2003)
Click on the OPTIONS button at the bottom of the screen (it's the last icon on the right)
Scroll all the way down the page until you see "Click View Items to view and recover items that were recently emptied from your Deleted Items folder. Recovered items will be moved back to your Deleted Items folder."
Click the "View Items" button and you should be able to browse thru a collection of recently deleted items.
Any item you restore will go back into your Deleted Items folder, where you can then recover it and put it where it belongs.