The application Event log errors you attached (copied below) are being generated by Unity's CsBMsgConnector service which periodically checks the USbms_ Exchange mailbox to see if there are any broadcast messages. The errors often indictive of a permissions issue. I suspect there are a diffrent set of errors in the application event log when you attempt to leave a message as you described in your post. Without seeing them, I can only guess that they are caused by some kind of permissions issue as well.
I would suggest running the running the Permissions Wizard.
Message 1: (Event ID 32013) Doh logon failed due to messaging component logon error: 8004052eH
Message 2: (Event ID 32012) An occurred which prevents successful Exchange access by CsBMsgConnector via MAPI.
This is typically an indication of configuration issues with Unity, Exchange, or the MAPI subsystem.
Verify that the Unity services accounts are granted the correct permissions and that there are no issues with installation. The SysCheck utility may assist in diagnosing the problem.
Message 3: (Event ID 30003) An attempt to access the Primary Exchange Mailbox Store by CsBMsgConnector via MAPI has failed. The MAPI subsystem return the following error: The information store could not be opened..
