To keep a long story short, I have about 12 VM's that are very important. I have had a total of 5 phone replacements since 2002, as I hang onto them until they are becoming pre-historic, voicemails were always on my new phones (as I think they reside on verizons servers anyways)
[...] What else should I try?
Nothing that I can think of. If VZW can't/won't help, I don't see what else you can do - the VMs
are stored only their servers, after all. (Strictly speaking, I'm sure they must have been backed up, presumably many times over 12 years, but as a practical matter, that doesn't mean you're going to get them to dig into those back-ups for an individual customer, even if you were willing to pay them probably an enormous/exorbitant amount of money to do so...) At one time at least, you
could pay them to make recordings of
current/existing VMs, but iirc even that service was overpriced for what it was, and I don't know if they offer it at all anymore.
Going forward: now that smartphone are the de facto norm, there are apparently lots of apps that'll let you record VM to your phone (not automatically, but while you play it, manually), or you can look for something like
this adapter (or just buy that one) to record them (or for that matter live phone calls) to an external recorder/computer. (Or check out
this page for a more DIY-type solution.) Those adapters used to be more readily available than they seem to be now (I still have one floating around somewhere that I bought years ago from Radio Shack for not very much money that worked OK, if not wonderfully), but if you're willing to sift through a lot of irrelevant search results, you might be able to find a cheaper one, too. The search I tried was along the lines of
[cellphone | "cell phone" recorder | recording adapter].
Is there a way to retrieve voicemails without using a voicemail app? I don't like using the proprietary program to retrieve messages, and would prefer to just download the audio, and listen to it using a program of my choice.
Do you mean, like a backdoor into VZW's voicemail system that would somehow let you just download the raw audio files, ftp-style?? I seriously doubt it, or (not that I in fact even know of such a thing,) at least not one that wouldn't involve potential criminal penalties for "hacking" if you got caught using it...