Hi everyone!
My wife figured this problem out. We both just got our GS5s today and we both had the same problem. We tried everything including the hard reset. She even turned off the notifications just so it would not annoy her. She tried to clear the data which was a temporary fix.
To skip to the good part, here is the clue.
If you long press on the notification a menu comes up "App Info". That shows you which app is making the notification. When she did that she was surprised to see that it was not the Voice-mail app rather it was the Phone app. She cleared the data on the Phone app and the notification is gone forever! It does not come back after rebooting.
This worked for me as well and I hope it helps others too. She is not an expert computer user but she tries things I would not think of.
I am glad she's my wife!