Youmail I used it, liked it, had to quit using it as when I was out of range Verizon would not answer by default making customers think my service had been discontinued. I couldn't have them think I couldn't pay my bill.
Google Voice is your friend. Good visual voicemail with lots of other features. Even got my voicemail over wifi when AT&T had the hiccups during sandy. Combined forwarding features with VoIP and never missed a beat(or a call that I wanted to take). Being a Google App, it is very well integrated into Android.