I am not sure I like the idea of VVM. Just recently, I had to switch from one phone which totally died to another, and I had critical voicemail which I understand would be totally lost if you had VVM. Seems like a bad system currently.
VVM, as implemted by Apple at least, was basically just IMAP-based behind the scenes. AT&T always had it tied to the SIM instead of to the phone number, so when you switched SIMs you were SOL with your messages. However, moving a SIM from one iPhone to another preserved your messages I believe. Since, as I said, it's just IMAP tied to the VM system.