I have a user who has random messages come up missing from his sent folder. Sometimes they will not appear immediately after sending them, then reappear hours later. Other times the message will be there and then disappear later, only to be shown again later. This happens on both his home computer and work computer running mail.app and also on his iPhone. We've verified that the filesystem on his computers are well and also rebuilt the message database in mail.app following the instructions in Apple support at Mail 2.0 Help: Messages can't be displayed or are incomplete or garbled

Our server is running 5.0.8 and doesn't display this issue with any other users. What else can I troubleshoot to determine the cause of this?