So you have checked the user's account under "Mailbox" and have seen that the size is zero? Keep in mind that tombstoned messages (that can be undeleted) are counted against the mailbox quota.
If that is showing zero, and if this is the only user for which this is happening, try changing the mailbox quota for that one user to a very high number and try leaving the internal message. If you are able, then Unity Connection seems to think the mailbox is full when it is not. If you have more than one mailstore, try migrating the user to the other mailstore to 'reset' the mailbox. If that does not work, I'd suggest using the Connection Message Archiver Cli to export the user's mailbox to see what Unity Connection believes is in there; or use the User Data Dump to export all information about the user and see what is up.
If, after all of that, there is no indication that Unity Connection believes that the user has messages in the Message Store, and you are still unable to leave a message internally, then you have a database problem and TAC would be the next step.
Maren
