I've been a longtime fan & user of Callwave, as evidenced by this blog, and this one (I haven't actually listened to a voicemail since May of 2007!). However, Callwave has moved away from the voicemail transcription business. Another very good (probably even better) alternative is PhoneTag, which provides very reliable voicemail transcription for something like $30/month. However, in the spirit of trying something free before paying, I've hooked Google Voice up to my iPhone's VM system. The transcription portion is definitely worse than PhoneTag's - probably 60% vs. 90%, but it's good enough for me to get a sense of who's calling and what they're calling about, so it's served my needs thus far.
Here's a video showing how I use some special settings on Google Voice to make it work with the iPhone's VM system.
Also, these GSM codes allow me to switch from AT&T's VM system, to Google Voice's:
Change VM to Google Voice: *004*1[your google voice number here]# (that's a number "1" and then your Google Voice number). For example, mine looks like *004*17029258528#
Change number of rings: **61*+1[your google voice number here]**10# (10 is # of secs, max 30. I have mine on 10 seconds, which is about 4 rings. For example, mine looks like **61*+17029258528**10#.
(Yes, using these codes for the first time is scary, but they work, and I'm sure you can call AT&T to reset your phone if you mess something up... well, don't take my word for that since I've never tried calling them, but I imagine you could!)