I have used both YouMail and Google Voice visual voicemail with previous phones and with the GNex. They are similar but each have some advantages and disadvantages, check them out. I started with YouMail, then later tried GV. I just recently decided I would stick with Google Voice and stop using YouMail, not that anything was wrong with YouMail. It came down to Google Voice's texting capabilities that made the difference. GV texting isn't great (SMS only, no MMS), but it is free and I am going stop using my Verizon number and the costly texting plan and just stick with my Google Voice phone number and free SMS. People can always email me if they want to sent pics or videos.
I looked all over for a visual voicemail app on my Galaxy Nexus before I found it in the market. Verizon has an app in the market called "visual voicemail nexus" or something like that. I have been using it since launch date and it seems to work better than the Verizon VV app that I've used on my last 5 Android phones.
I don't know if it will do what you're looking for, but it is another option for VV.