I I know this doesn't really answer your question, but have you tried google voice? I've been using that for my voicemail instead of at&t voicemail and I think it's just like visual voicemail. It shows a list of messages, and let you play them individually. It's also got the benefit of getting voicemails on your computer.
Sent from my Galaxy Nexus using Android Central Forums