[HybridAndy]

Go to Settings > All Settings (left shoulder button) > Personal Tab > Phone

At the bottom bottom of the screen is a Voicemail box. I just added a p1111 after the *86 and when I call my voicemail, it waits a moment and then enters the pin. I've been doing this for my last 3 phones and it's worked great for me (my pin is not 1111 by the way).

I actually have a number in my address book that calls my office voicemail, pauses (p) enters my extension + #, pauses, enters my pin + #, then hits 3 to go to new messages. The numbers looks like

800.111.1111 p 1111# p 1111# p 3

Looks strange but works like a charm, especially useful with a bluetooth headset since I can check for new messages without touching the phone.