When you have a message on your voicemail, the dial tone changes to a stutter tone. Your modem interprets this as no dial tone, and will not dial out.
Add or change this line in /etc/wvdial.conf:
Abort on No Dialtone = no
This tells WvDial to dial no matter what, without checking for a dial tone.
Hopefully, you are not in the sort of environment where phone cables are continually coming unplugged, which would make using this option a bit of a problem. You might want to turn up the modem speaker so you can hear it dialing out, just to keep an eye (OK, ear) on it, with these options added to the Init2 line in /etc/wvdial.conf:
M1 L3
M1 turns on the speaker for
dialing and the handshake only. L1
is the lowest volume. L2, L3, and
L4 are progressively louder.
man 1 wvdial
man 5 wvdial.conf
man 8 pppd