Mika1973, let's make sure we get your voicemail notifications back! When did you start noticing this occurring? Are you using visual or standard voicemail? Please share a few more details so we can find resolution for you. Thanks!
Follow us on Twitter @VZWSupport
If my response answered your question please click the "Correct Answer" button under my response. This ensures others can benefit from our conversation. Thanks in advance for your help with this!!
You might try going in to Settings>Apps>then you should get a list with "downloaded" at the top,... swipe from right to left until your list says "all" at the top, scroll down the alphabetical list until you get to "voicemail", then tap on voicemail app, then make sure box saying "show notifications" is checked. If not, check it, If its already checked, tap on clear data, and then force stop.