It's a 4-month old thread, but I thought I'd contribute in case anyone's Googling this issue. I have a Samsung Galaxy S6 Edge 64GB which I just purchased and which had this problem....
Called my carrier, Bell Mobility in Canada, and they solved the issue by deleting/re-creating my voicemail box. They sent me a voicemail prompting me to set up my new voicemail and after I had set it up and deleted the voicemail the icon disappeared, even after a reboot.
I've had to do this with my BlackBerrys before and the carrier did the same thing to clear the notification. Not a Samsung-specific problem I would say!