I wish I had good news.
Do you turn your phone off a lot. Each time your phone is turned off it will tell you you have received a new msg even if you haven't. This voice mail thing is some kind of glitch in the system. Don't know if it's android or Samsung. So yeah, it's a pain.
Hello Chew, I've tried to follow your second option, but it still didn't work for me. So I changed a little bit the part where you select the phone apps, instead, I selected the "call settings" app and then clear the cache and the data as well. This little modification worked for me. Thanks a lot for your sharing.
If you would like to reduce this notification to almost nothing then i have the best solution to permanently reduce this notification
Inside of the phone app go to settings>voicemail>notifications>and silent and minimize them, this hides the voicemail notification unless you expand the notification panel then it there but minimized