I recently encountered the same problem. I was using google voice for my voicemail with no problems on my Samsung Galaxy s4. However, after encountering some problems with my google voice mail, my voice mail notification appeared for the first time and will not clear.
After much reading, it is simple to clear. Just go to settings, application manager, slide the bar to "all" and then go to phone and hit clear data. That should get rid of the phones voice mail notification without rebooting and no change to your phone contacts.
However, I just rebooted my phone and much to my dismay the same voice mail notice indicating I had 3 voice mails reappeared and would not clear via the "clear" button.
I simply went back to application manager, and cleared the data on my phone and the notification is gone.
As I think about it now, I think the answer is simple. The reason I encountered the problem in the first place is because my google voice stopped working so I activated the voicemail that came with my phone. When I called to test the phones voice mail, I was surprised to hear that my message bank was full. (I never used the phones voice mail system) I then deleted every message on the phones voice mail except three test voicemails that I left after deleting all others. I then reconnected google voice mail as my default voice mail and it worked fine but the same message that I have 3 voice mails remained. I think my mistake was not deleting the three test voice mails I left after deleting all the others.
So here is my suggestion. Either, go to phone and clear data every time the voice mail notification appears and will not go away. Or, reconnect the voice mail service that came with the phone and delete the open messages you are receiving notifications about. Then reactivate google voice before you get another call that goes to your phones voicemail.