Can the user dial into the voicemail pilot, login and get to the message? or is the message not there either? How about the web box? If you disable the unified messaging for the user does the message stay put?
If the message is not there, I would check to make sure that "message actions" under the user setup is set to "accept" and not "relay" in anyway. Perhaps an accidental change was made on the user. If the setting is not "accept" then it would stay on the voicemail store, it will be removed as soon as the email is sent somewhere. "Accept and relay" would also keep it on the store.
You can check Unity's view of the message waiting indicator under the user's mailbox settings in "Message Waiting Indicator" to see if it thinks it is on or off.
Did you very that the user did not setup any rules on the Exchange side that could be interacting with the message and whooshing it away to a sub-folder or something?
