This can occur due to a malfunction of AvMsgStoreMonitorSvr service.
This issue can be resolved by stopping and then starting the AvMsgStoreMonitorSvr and AvUMRSyncSvr services on Cisco Unity. Perform these steps:
Note: AvMsgStoreMonitorSvr service applies to Cisco Unity 3.1(5) and later versions.
For additional information, refer to Cisco Unity Service and their Functions.