i am so done with verizon's voicemail!
ive been using callwave for months:
Receive cell phone voicemail in email with CallWave Visual Voicemail

the service, among other things, will email you a .wav of a new voicemail...
that wav plays fine in my 8830, so i dont even waste a 2 minute call to check my voicemail!