ok, this took some digging, but i found it. if you go to the store on apple.com and click on the iphone, under the options for selecting which phone you want (4GB or 8GB), there is a section called "at&t rate plans for iphone". click on "learn more about plans and activation" at the bottom of that little section, it opens up a new window. on the left in gray are various subjects, pick "data and SMS". the 4th question under this subject is about whether or not visual voicemail erodes your minutes. the answer is no, it goes against your unlimited data plan. at&t apparently converts your voicemails into sound files, which are sent to your phone by their data network.
now if you actually CALL your own number from your iphone to access voicemail, then yea, it uses minutes, just like any other cell phone.