FWIW, I've been using the tethering hack from http://help.benm.at on an iPhone 3GS and visual voicemail has been working just fine.