This information applies to at least Exchange 2003; I can’t verify any newer versions.
Sometimes an item in Exchange has been perminently deleted, and doesn’t show up in “recover deleted items”.
You can find these items through the OWA interface, if you have it enabled.
Paste this into IE, filling in the server name and user alias.
https://server_name/exchange/user_name/inbox/?cmd=showdeleted
This will show different results than what you would typically see using “Recover Deleted Items” from within Outlook.
