I have notification on my EVO that I have a new message, when I check, there
aren't any new messages.

What I have figured out is that I have rules set to re-direct messages
depending message content to folders. What appears to be happening is at
random, a rule executes moving the message to a folder and for a split
second that message appears on my device inbox triggering the notification
but then that message disappears.

This has only started with the last couple releases of Mobility.