All voice mail systems have a finite amount of space to work with when it comes to storing greetings, messages and custom menu recordings. As mentioned above your problem can usually be attributed to one or more overflowing mailboxes.
End users should always be trained to check their mailboxes regularly and to delete their older messages to prevent the kind of problem you seem to be experiencing now. Class of service restrictions can prevent them from storing too many for too long.
Many times when we hear this complaint we find that there are dozens of former employees still on the roster with active, overflowing mailboxes.
If you are the authorized system administrator for your company or organization, I would recommend scrolling through all of your mailboxes and delete any that are no longer in use. Of course that could remove hundreds or even thousands of massages, some of which may or may not still be valid and important so you may want to check the newer ones first and forward the important ones on before doing any mailbox deletions.
It is not at all uncommon for a technician to find a thousand or more messages stored in the general delivery mailbox when this happens (often because it's assigned to the wrong phone) so that would also be a great place to start if that applies to your situation.
The general delivery mailbox is usually the only one that doesn't match the extension number. If your system has 3 digit extension numbers, your general delivery mailbox will be number 100 and it is typically associated with the extension at the front desk. On four digit systems it's mailbox 1000.
If you don't have a trained, designated system administrator, your authorized vendor should be able to help you and/or train you and you may never have that problem again.
Good luck and let us know what happens.
Phonehed in Dallas