I tried all of the options listed and nothing worked. I finally turned off the phone, removed the SIM card and memory card, turned on the phone without either inserted, turned off the phone, re-inserted the SIM and memory card and turned back on the phone. FINALLY that notification is gone.
Great suggestion and it worked. Infact this has been on my Note 8 for 5 months. Today I switched to the Note 9. When I switched my SIM card from the N8 to the N9 the Voice mail icon moved to the new phone, even though I have not recieved any voicemails yet. I suspect the carrier messaging system may have somthing to do with it. Thank you so much.