I feel your pain, conrail. I've had similar problems occur with our Outlook.
1) Days ago one worker received and read an external email. According to her, after reading she simply closed the email, but yesterday when she checked her Inbox is was not there. Again, she said she didn't delete the email, however we had to use the Recover Deleted Items function to find and retrieve the email. It's as if the email deleted itself twice.
2) Another worker has been sending various emails to her manager (internally). For some reason some of these emails end up in that manager's Deleted Items folder or - like with example #1 - completely deleted necessitating the use of the Recover Deleted Items function here as well. In one case, the email message is completely missing and can't be found or recovered.
I'm trying to figure what could suddenly cause these things to happen? We are using Exchange 5.5 over NT 4.0.