Q: Voicemail will not stay deleted

To ChrisJ, sounds like you're being kind of snarky, insisting this is a carrier issue & not acknowledging the possibility of a software/hardware malfunction. No offense, but this has been heavily reported across the forums.
I've been reading and researching this the last several hours on various threads, and users have complaints from all carriers (AT&T, Sprint, Verizon, T-mobile) and even in some cases past issues with different iOS and iPhones... one thing is consistent - it is the iPhone. So let's move on.

To all, several suggestions are reported with varying success amongst users:

A) Delete 1 voicemail. Scroll down to bottom, select Deleted Messages, Select Clear All for the 1 voicemail. Repeat. (basically delete then delete, one at a time. This one worked for me!)

   A1) If the "Clear All" is greyed out at first, select then deselect the message, and "Clear All" should be blue and selectable.

B) Call AT&T (or whoever your carrier is) and request them to "reset your visual voicemail" or a "voicemail system reset". Reference this help thread if you need to (see note by Brucku). Solved for 2 other people. The thread is here:

https://discussions.apple.com/thread/5327914?start=30&tstart=0

C) Call your own voicemail manually (call 1 or call your own #) (circa early 90s) and delete each message manually through the voice prompts (press 7 to delete, for AT&T at least). You may need to make sure to "listen to saved messages" as some are lurking in there. Reportedly solved for quite a few, but not working for many others.

D) Something convoluted about deleting the Visual Voicemail message, then Clear All, then enter Airplane mode, restart the phone (home + power button), then turn off Airplane mode. Few said worked, but most said it didn't. (I tried several variations of this to no effect).

E) Reset "Network Settings". (note: this will reset wifi passwords, but phone is fine just don't Reset All!) Reboot phone. Delete messages as you would. Worked for some.

F) Drop iPhone in toilet. All Visual Voicemails should disappear. Works for all who are willing to part with phone.

Hope this is helpful. So far sol'n "A" is working for me, and this was affecting 2 phones in my household. Will update if it reverts and I have to do "F". Cheers!!

Hey guys, I did FINALLY get Apple to admit that this is an issue.  I have called them over the last 45 days 5 times and each time asking for that persons boss.  I finally got a senior tech that admitted they are aware of the problem.  They are working on it but at this time they do not know what it is.  Something to do with all their carries software not playing nicely with IOS7.  She assurred me they will have a solution soon.  She even emailed me her direct contact info and I told her I would try and let everyone know about on the forums I was a part of. 

I am having the same problem .. Iphone 5S .. IO7 .. AT&T.  Frankly, I am comforted to see that I am not alone in enduring this inconvenient glitch.  I had the same thing once before with a previous iphone.  It was 5 years ago this month.  I tried everything and zeroed in on AT-&T as the problem.  Went round and round with their high level tech people.  They gave up.  I gave up and took my number and switched to Verizon.  Voila .. no more voice mails refusing to stay deleted. 

However, I hated Verizon .. had even more dropped calls with them than with AT&T here in Jacksonville, Florida.

Switched back to AT&T and did not have the problem any more .. until now with the 5S and OS7.

I'm going to the AT&T store to see what they say. I'll keep you posted.

I'll update my original post, as the solution of "Delete one at a time" was working for a while... then the voicemails came back.

I resorted to option B:

B) Call AT&T (or whoever your carrier is) and request them to "reset your visual voicemail" or a "voicemail system reset". Reference this help thread if you need to (see note by Brucku). Solved for 2 other people. The thread is here:

https://discussions.apple.com/thread/5327914?start=30&tstart=0

I used the AT&T tech support chat via the website, so I could cut & paste the above link into the chat. You have to specifically request to "Reset your Visual Voicemail" also known as a "Voicemail System Reset". The tech I spoke to had not done it before, but was able to do it based on my description above. He had to ask someone else. He then warned me it would erase all saved voicemails and reset my greeting (great!). Took a few minutes, then once done took about 10min for the system to clear up. Had to reboot the phone after it was complete.

Voila, no phantom voicemails for me. (for now, fingers still crossed it doesn't recur again, but it seems to be working much more smoothly now.

Best of luck & hope this helps.

Funny how you were able to resolve this by contacting the carrier, when you said I was being "snarky" by saying it was a carrier issue. I had dealt with AT&T about this issue and was advised of this at one of their corporate offices. Otherwise I would never have posted that information. I've been an AT&T customer for years.

In the end though, I'm not offended by your reference, and am glad you got your situation taken care of.

I was having the same issue with 1 pesky VoiceMail. I tried what TedBoosley stated to do: I called my own number and got to my voicemail, hung up, was then able to delete message. Thanks TedBoosley

Message was edited by: LTA85 - grammar

Thanks so much! I had this one voicemail from my orthodontist that was bothering me for the past couple of hours because it wouldn't delete. A while ago I tried what you did and it worked. So thanks again!

I had this issue last night on my iPhone 6 (Verizon) running the latest iOS 8. This was the top post that came up when I was looking for a resolution. What I ended up doing was:

1. Place phone into airplane mode

2. Delete messages

3. Reboot (while still in airplane mode)

4. Turn airplane mode off after reboot

The last two steps may not be needed; I did them as a 'just in case'. At any rate, afterwards, I left myself a voicemail and it showed up and I was able to delete it as normal. Hope this helps.

This totally worked. I tried calling my phone and getting the voice mail to no avail. I tried ever other 'cure' people swore by and none of them worked. But this one DID!  I have no idea why putting your phone in airplane mode and them deleting the message would get rid of it permanentl, but it did. I also shut my phone off and restarted it after this while in airplane mode just to be go the extra mile. Thank you very much for this tip!  It has gotten rid of a message that has plagued my inbox for almost a year.

Thanks. Worked like a charm!

Worked! Thanks