I've had a similar issue, although these were calls from a cell phone to the VM and not as common as the "many times" you are experiencing and the messages were not "cut-off" but stopped with the VM prompting to save, replay, etc.
This was corrected by adjusting the DTMF Detection Information within the Voice Processor settings.
In a sense the Voicemail was picking up frequencies or tones that it processed as the caller dialing digits.
I would look at the voicemail logs before I went through the replacement process.
