Hello,
I don't have an exact reason but at least something to check.
http://www.cisco.com/en/US/partner/docs/voice_ip_comm/connection/7x/troubleshooting/guide/7xcuctsg160.html#wp1056633
Message Notification Received When There Are No Messages
When users are members of a distribution list that is the recipient of a call handler that is configured to mark messages for dispatch delivery, it is possible for a user to receive a message notification for a message that no longer appears in the user inbox when he or she attempts to access it. This can happen because another member of the distribution list has accepted the message between the time that the notification was sent and the time that the user tries to listen to the message.
When configuring message notification rules to include dispatch messages, make users aware that by the time they receive the notification and call in to retrieve the message, it may be gone from their mailboxes because another user has already accepted the message.
For more information on dispatch messages, see the "Dispatch Messages" section in the "Messages" chapter of the System Administration Guide for Cisco Unity Connection Release 7.x.
One thing that might be interesting to check, does MWI agree with there are no new messages. You can check this on Message Waiting Indicators page under user. If that does not show the correct status you might have something else going on.