Iphone 5s Visual Voicemail delete issues with ATT

I upgraded my 4s to a 5s in Oct after hearing about software bugs in putting Os7 on an older iphone. From day one, my voicemails kept reappearing after being deleted. I have to deleted them on average 6 times, from the visual voicemail box AND the deleted voicemail screens (so 12 times per voicemail) in order to get them to fully detete. This is a problem because I get a ton of voicemails per day and my box was filling up quickly. I don't have time to deal with this over and over and over, I am at my wit's end.

Here is what I have tried over the course of 2 months and over 35 hours on the phone and live with ATT and APPLE both (apolgize if it's not the proper terms, I'm not a techy person): Also, I've tried it all of these fixes multiple times to ensure I"m doing it properly.

All of the fixes noted in another thread here including:

1. power off while in airplane mode, delete messages, power pack on, turn airplane off.

2. deleted them by calling in directly by pressing and holding 1to access voicemail system.

3. delete them one at a time from voicemail inbox, then from deleted voicemails (and doing this by various ways to delete, either the delete button while it's expanded OR the swipe delete option, also using clear all, and using the swipe clear way of doing things)

I have also tried:

4. Reboot network settings from within iphone several times

5. restoring to factory settings several times

6. restoring from backup several times

7. putting my simm card in a completely new iphone in the store with ATT rep (they said it worked, so phone was issue and sent me to APPLE, but only tried it for a few minutes and it typically takes anywhere from 30 seconds to 5 minutes to half hour to half day for them to reappear.)

8. complete new phone with my simm card (by APPLE, still had problem, so gave new phone back)

Att blames apple, apple blames att. I don't care who's fault it is, it's both their problems. I tried to take iphone 5s back in order to go back to my 4s and ATT won't take it back because I'm long past the 14 days "Buyers remorse" return period. Even though I advised them of this issue and it's imortance to me well within that time frame, and I have been patient for 2 months waiting for a fix. I'm done being patient, I need a solution now.

Att refuses to take phone back, or allow me out of contract without fee. Apple will take phone back, but then I'm still faced with $350 termination fee from ATT (who won't waive it even with this long history of issues and my 10 years of giving themmy money). So no matter what I do I'm out a significant amount of money and I still don't have visual voicemail. Plus even if I do that, I've heard Verizon users have same visual voicemail issues.

So what is the solution? I need visual voicemail and my gmail on my phone preferably not web based but through the phone.

If I've missed any fixes or solutions, please let me know what to try. I can't deal with this any longer I'm at my witt's end and no excalated level of APPLE or ATT can solve this.