Skype has always served me well (though I’ve admittedly only played with it). It’s a good OS X citizen, sporting a great interface and utilizing some neat OS X software like Growl. However, you have to pay for the voicemail service. You don’t have to with Gizmo (an interim name). Gizmo has both a Mac and Windows version. A Linux version is in the works.
Anyway, I’ll be playing with it. If you want to download and give me a call, drop me a line so I can prep myself.