Am I correct Visual Voicemail does NOT use any voice pkg minutes?
checking visual voicemail (through the visual voicemail tab in the phone application) does not use minutes, it uses data. you'll notice that when you don't have an edge signal and you go to the visual voicemail tab, you get an error that states visual voicemail is unavailable, and your only option is to place a call to your voicemail box to retrieve your messages. you can listen to visual voicemail messages only when you have an edge signal since that's how they are downloaded for listening.
of course, when you make a call to check your voicemail messages, that is an actual phone call. but, iirc, these calls are noted as voicemail retrieval on my bill and are not deducted from my plan minutes (i'm with AT&T on an official iPhone plan)...