^^I believe that's right. I was using Google Voice for voicemail, but decided to switch to VZW's voicemail service for ease-of-use.
I had a free trial of Visual Voicemail, but there's no way I was going to pay monthly for it. After the trial ended, that same "Voicemail" app still provides my basic voicemail, and I believe any voicemail left over should just be converted to a "basic voicemail."
Otherwise, if that doesn't work, you're probably going to have to contact Verizon and see if they can delete it from the server for you. I'm not sure they allow their basic tech support people that kinda power, but if you can't clear it on your device itself, you're still getting the notification because the network is telling the phone that you've still got a voicemail.