On AT&T, this screenshot should answer your questions on Visual Voicemail: not available before Nov 15th
I had to call AT&T CSR to roll back my unlimited data plan, that they changed to a 3GB plan when I upgraded my phone (very annoying) and then I had to call back to ask with the VVM was not working.
Then they activated the unlimited data plan with VVM
So many things !!!!!!!!
Love my Lumia 920
(by the way, pre-ordered on the phone on the 7th and got it by express FEDEX on the 8th, before the wireless pad charger)