After doing multiple troubleshooting calls, for at&t, and now seeing that other carriers are having the issue, let's take a look at the constants.
1. iPhones with iOS 7
So, we have determined that BOTH GSM & CDMA phones are having the issue. The one constant is the iPhones, that iOS 7. Well, after browsing Apple's support articles, I found a new addition to iCloud Backups. iCloud will backup Visual Voicemail. The reason, that the messages keep coming back, iCloud is re-synchronizing them to the phone. Period. If it were only the at&t network, I would say call us. You may still have to, if you are a novice, with your phone.
Here are the steps to resolve the issue: Step 1: Turn off iCloud backup.
2: Backup your phone in iTunes(Since we know how iCloud loves to remove its sync'd content from your phone).
3. Delete iCloud from your phone(keep sync'd contacts on the phone)
4: Reset All Settings(not just the network settings)
5: Delete VVM from device.
6: Problem Solved
I have done these very same steps, on multiple iOS devices, and have had a 100% success rate. For the record, for those that wish to blame the carriers, when the VM box is deleted as a featured, ALL voicemails are deleted from the network. If you have a new VM setup, from your carrier, and your old ones come back, well by process of elimination, it has to be a bug on the phone and software.