Have you tried pressing and holding 1 to see if it works that way? truthfully i would have called vzw first instead of coming onto a forum to get it figured out. Especially if it has taken a week for you to say i will try that...
What about the voicemail playing, stopping, playing, stopping on its own, or disappearing and coming back make me believe that it is a Verizon problem? It was on the phone, you could see the VM, who it was from and how long it was, but there was always an issue when trying to get it to play correctly. That sounds more like a phone problem, and not a network issue. However, I will give that a try. And it is my wife's phone, not mine, so I don't constantly have it with me. I thought there might have been a quick fix that someone else had dealt with.
And, maybe if I hadn't re-herniated a disc in my back this week causing me to have to get surgery on Tuesday, I would've already gone to VZW. But that's hard when you can't drive yourself and have to travel back and forth 150 miles to your doctor.
Hope that explains why I came here first.