Do you know which voicemail system is being used?
If it is an Avaya/Lucent/AT&T product, it could be a Partner Mail (old stand-alone unit that looks like a wall-mounted PC), Partner Voice Messaging (looks like a PC card located on the front of a Partner ACS processor), Partner Mail VS or Avaya Partner Messaging.
All of the above voicemail systems (except the Partner Voice Messaging) use a hard drive, while the P.V.M. uses, I believe, memory chips.
If the voicemail system has a hard drive and if the distortion affects all users, I would guess that the drive is about ready to go "toes up" especially if a reset of the voicemail and processor fails to fix the problem.
Replacement drives can be purchased from online dealers. However, if the voicemail is an old/obsolete model (Partner Mail & Partner Mail VS), it might make sense to upgrade to the current Avaya offering, the Avaya Partner Messaging R7, assuming that the processor can support it.
The following link is a listing for the A.P.M. R7. Down towards the bottom of the page, it lists which Partner processors will work with the voicemail. Is the customer's processor one of them?
http://metrolinedirect.com/pamer70.html