Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Yes, it's still stored even though you deleted it. You must go into the deleted folder and delete it again haha. It's a terrible feature for VVM and they should get rid of it. I like it for things like email when you have a huge storage limit and space isn't an issue, but for this, it's terrible.
 
I had the same problem. The problem existed from my changing a carrier file and the settings trying to get MMS to work. (it failed)

Go into
Settings-General-Network-Cellular Data Network

Make sure your "VISUAL VOICEMAIL" is set as this
APN: acds.voicemail
no username
no password.

Now you should go back into your voicemail and see a ton of them there again. Just delete them again. Then go into the deleted voicemails and clear them out.
You may have to restart the phone, I didn't have to though.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.