I just found this article from David Pogue that indicates how to avoid the voicemail prompts and greetings:
It turns out that each carrier offers a “bypass the instructions†keystroke that takes you directly to the beep. (It bypasses both the person’s own recorded greeting and the 15-second carrier nonsense.)
To be as evil as possible, the carriers do not promote or tell you about the existence of this keystroke. Furthermore, the key to press is different with each company:
* for Verizon
1 for Sprint
# for AT&T
# for T-Mobile