This may be more than you're willing to do, but you could get a Google Voice number and associate your current cell # with it. Google Voice can give you visual voicemail.
has verizon eliminated vvm completely? my understanding is that they only got rid of premium vvm for older devices. but you can still use basic vvm.