I have seen this when an overzealous administrator starts playing around with archiving. But I would need more information to diagnose your specific issue. Is this happening all across your exchange server? For one or more users? How are they connecting to the server?
Have you tried restoring the messages from backup?