How to delete voicemails?

I am having the same problem. Using the latest ios7 update on a 5S.

I "delete" for each individual VM and then go to the Deleted Messages folder. Once in the Deleted Messages folder, the "Clear" is grayed out until I select one of the messages. Once a message is selected and then unselected (tap once to select, tap again to de-select), then the "Clear" turns blue and will function.

However, some period of time later, sometimes seconds, sometimes minutes or days, many of the VMs re-appear on my VM screen.

When you delete a voicemail a signal gets sent to the carrier to delete it from their servers. If you don't have a cellular connection when you delete the VMs they will not be deleted from the carrier's server and will be reloaded. If you are sure you have a cellular connection when deleting contact your carrier, as it is their problem.

I'm having the same issue - it is recurring. Apple, please issue a fix for this. I've deleted the same messages so many times now.

I am on an iPhone 5s with the latest iOS 7.0.4 update and I am having an issue where deleted voicemails recover even after permanent deletion. I even logged into the VM directly though a land line and deleted with the prompts and they still recover.I had ot have ATT delete my voicemail box since it is full and I use for business. Anyone out there know when ATT and Apple will quit pointing the finger and get an update that fixes the issue?????

For eveyone here having ATT delete your VM box and restart does the job.....