i was just talking to an agent about this today.
you should have Visual Voicemail feature on your plan and phone. Ask them to sync your account.
ok here's what they told me. There's one central voicemail server. Either you access it by Regular Voicemail which means you press 1 on your phone, OR Visual Voicemail. Whatever way you access it, Regular Voicemail or Visual Voicemail, you're basically going to the same voicemail server from your provider. Now, if you delete, you're deleting from the server itself. Also, the server only hold saved Regular Voicemails for 30 days. However, I realized that if you do Visual Voicemail, it gets saved in your phone itself. So basically right now, i have Visual Voicemails older than 30 days saved on my phone. If i saved this on my Regular Voicemail, I would've lost em after 30 days grace period.
That being said, you cannot bring old Visual Voicemails from your old phone to the new phone because it is stored in the old phone itself. So in my case, my Visual Voicemails saved from my iphone 5 cannot be transfered to my 5s. i tried back up and it didn't get backed up.