I have a user that will get his notification that new mail has arrived, would you like to open it. When he clicks the OK button on that message, a new message pops up saying that "The message has been moved or deleted", and there is no new message. This does not happen with all of his messages just periodically. I am running Exchange 5.5, SP4 with Outlook clients. He has no client side or server side rule setup.