I think we’ve established that at the time this question was asked, you were left at the mercy of your carrier. There were workarounds, such as plugging an AUX cable into a computer and recording those voicemails, but many of them were rather cumbersome or lossy (or they cost money).
Thankfully, starting with iOS 9, Apple added the option to convert Voicemails to Voice Memos (on carriers that support Visual Voicemail).
Simply open the Share Sheet on a voicemail you want to save, then select Voice Memos
.

Voice Memos are supposed to sync via iCloud (although my results have been spotty with that one), and my experience has been that they get included in your iTunes and iCloud backups as well.
You can also save your voicemails to iCloud Drive, AirDrop them from your old iPhone to your new (although that requires at least an iPhone 5), etc.
I don’t know how relevant this question still is to the OP, but if they kept their old iPhone 4s, it is eligible to upgrade to iOS 9, and therefore transfer those voicemails that have been sitting around all this time.