I've experienced like this article states
Why are voicemails backed up but not restored?
I got an iPhone 5S and created an iTunes backup of my i5 to transfer over. Everything except voicemails are sent over.
Out of 40 voicemails, only 5 or so are transferred. Basically only the voicemails that are live on AT&T have transferred, im assuming the rest auto deleted themsevles (I think AT&T only retains them for a short time). However I've taken a backup extractor and can see ALL of my message are indeed present in the backup. I know I can export them to my PC but is there any way to get them to restore to my new device?