The user is unable to view deleted items in his deleted item's folder. After an item is deleted it disappears or in some instances is not moved. Serveral people have access to his mailbox and even they have the same issue. We suspect that the server automatically deletes the email permanently, however nothing was ever changed. We checked any instance of this problem and came up with nothing. He manages all his email on his Blackberry. At first we thought the issue was connectivity to and from his Blackberry but the issue occurs even with other people who have access to his mailbox. The mailbox is hosted on an exchange 2003server, specifically ver 6.5 build 7638.2 SP2.

Have you tried deleted item recovery? When the deleted items folder is highlighted, go to tools menu, then recover deleted items.

Yes I tried recovery, still nothing.

Here is a copy of a registry fix that I use in my environments, which saves me from recovering individual messages from backup. I call this registry fix "Dumpster On". It is an Outlook registry fix that allows a User to retrieve messages that was deleted from any folder in Outlook from the Exchange Server. Of course, the message is only available for the length of your "Deleted Item" Retention Policy on the Exchange Server. Just save the file below as a .reg and restart Outlook. To recover a file, select any folder inOutlook, and then go to Tools, Recover Deleted Items. REGEDIT4 [HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Exchange\Client\Options]"DumpsterAlwaysOn"=dword:00000001

I used to have the problem,you can try try this tool ,Advanced Outlook Repair can help to undelete the emails you delete by mistake. Refer to http://www.datanumen.com/aor/problems/outlook-deleted.htm for more detailed information. And visiting http://www.datanumen.com/aor/ can get detailed information about Advanced Outlook Repair. And you can also download a free demo version at http://www.datanumen.com/aor/aor.exe