This worked really well for me. I am not affiliated with the company in any way, FWIW. I accidentally deleted all of my voicemails by tapping Clear All when I was in the Deleted Items view - it somehow deleted not only my deleted items, but everything in my inbox. This included precious voicemails from my late father-in-law. I tried a bunch of different ways to restore them (Backup Restore, file system utilities, etc.) with no luck. I decided to try Decipher Voicemail and it totally worked. There is a bug that prevented .amr files from being associated with a new app after I changed the association, but converting to MP3 worked. I also now have local copies of all of my voicemails from my backups on two phones, one of which died a couple of years ago, but I still had the backups.
Thanks for sharing this solution - I have all of the voicemails permanently archived now and accessible.