I am thinking that perhaps you have over-subscribed your voicemail systems storage limits. You've not specified what voicemail system you have (presumably it's CallPilot)... do you have the reporting module installed? Can you either (a) run a report or (b) do some math and figure out whether your users have more voicemail storage allocated than is available on the system?
Example:
I have 30 users. I have 10 hours of storage. I give each users 1 hour of storage. I have over subscribed my storage capacity by 20 hours (30 users * 1 hour each = 30 hours > 10 hours of physical storage available)
If that happens to be the problem, then reducing the storage limits for all other users would resolve the problem... (Assuming it's a recent version of CallPilot you could just review each Mailbox Class of Service for the storage limits per mailbox, then multiply that by the number of users associated with that VMB COS, then total those values up and determine if you are in excess of the storage capacity on your hardware.)
You would also want to review the configuration on each VMB COS that specifies voicemail retention. I would set it to purge read voicemail older than 7 days for a short duration (a week or two)... this would "age out" old, read voicemail.
Naturally, if you change mailbox retention, you should communicate to users that they may lose valuable voicemail and to start transcribing anything that is needed. (Also, you could perform a voicemail backup prior to making the changes and then keeping that voicemail backup handy for 30-45 days in case any purged voicemail turn out to be business critical.)