Hello -
I just had this happen to one user on our Unity 3.1(5) system - integrated with CallManager 3.3(2). I found an application log event indicating the user's mailbox was full, followed by the information "The subscriber cannot send or receive new voice messages until mailbox size is reduced. " While the user's mailbox was in this condition, she sent a voicemail message to another subscriber. The voicemail message showed as coming from Unity Messaging System - servername, not the subscriber. The subject of the note was "Message from an unidentified caller (66113)". Not sure if this applies to the problem you are seeing, but in our case I believe the full inbox was to blame. I am following up with the customer's administration staff to see if this has reoccurred. Will report back here.
Sincerely, Ginger