This is a strange problem as I've not come across it before either!.
Are the gaps in the voicemail message at the start, middle or end etc?. Are they all at around the same point etc?. I think the last system patch update was 034 and the desktop was 020.
BCM 4.0
==================================
PATCH ID: BCM.R400.359-ROOTFS Category: LTD
PATCH ID: BCM.R400.140-AASpecializedTransferActivate Category: LTD
PATCH ID: BCM.R400.SU.System.034-201206 Category: GEN
PATCH ID: BCM.R400.SU.Desktop.020-201203 Category: GEN
I think there was also a small CTE patch released which is available here if you don't have it.
BCM.R400.340-CTE-1.5-1.0.zip
I don't somehow think it is patch related. It might be worth having a few backups done and perhaps using another hard disk with 4.0 software on it to see if the problem was the disk.
Firebird Scrambler
Nortel Meridian 1 / Succession and BCM / Norstar Programmer in the UK
Advance knowledge on BCM support