I'll bump this up too...
We have had issues with clients using IMAP from multiple devices to the same account.
It in particular seems to involve iOS and its default mail client and another device using Outlook as its email client.
Still working out all the details on the issue, but in general...
The mail will get delivered to the iPhone, but never appears in the Outlook desktop client.
With no ability to see what messages were deleted (and by what IP) we are stuck "assuming" that that is what the client did (deleted the message from the iPhone then the Desktop client never even saw it). But... we cannot PROVE that is the case.
As an FYI, this has been more than one account with the same configuration and the same issue.