I swear by GrandCentral, with a runner up to Callwave, GrandCentral is a free service that gives you one phone number, which can ring through to like five or six phone lines. They also can email you or text your notification to you. There is a mobile web interface, which allows you selectively listen to messages a la iphone visual voicemail. They also allow custom greetings for different callers. They also claim to archive your VM"s forever. You can switch calls between phones, record calls, and screen callers while they are leaving a message. Kinda freaks people out when you answer in the middle of a message like the old answering machines. I have cut way down on cell minutes, because I can use my Vonage line at home, or even transfer/answer calls on gizmo's VoIP service. GC transfers to Gizmo as a SIP call, so there is no fee from Gizmo.
Callwave is another service that will email you a .wav of your voicemail, using your own line. I get an email from them in my inbox, then open the wav whenever I get to it. It has the caller info and length of message, so you can kinda tell if it's important.
GrandCentral.com and calllwave.com Check them out!