If the problem hasn't been solved yet, have you considered that someone else may have logged into the guy's pc and downloaded and deleted his emails. Also, what happens when you send him a test email from an external account? What about from an internal account? Do both emails get to his inbox? On an even more sinister note, is it possible that someone used either IP/MAC spoofing or some kind of a MiTM (Man in The Middle) attack to get the email as it traveled between your server and the client? What about ARP spoofing (unlikely, I know)?

Cheers,
cgkanchi