I've had the Galaxy SIII since it came out on Verizon, but I have not once received a voicemail notification. I thought this might be because no one likes me and I rarely get phone calls. However, after not receiving the birthday voicemail my parents swore they left, I checked it. To my surprise, I had several new voicemails! It seems I am not so alone after all.
I have fiddled around with the settings and poked around the interwebs, but to no avail. I can easily find the setting to remove the notification, but that is, of course, not my issue.
I can't always get to my phone so I rely on my voicemail notifications, too! I completely understand the importance of having that icon pop up for you! Although, mrsdawg2 and maya0630 both provided some helpful information, it looks like you've already taken these great troubleshooting steps. I would like to recommend resetting the Voicemail application on your Galaxy S III:
• From the home screen, select Apps (located in the lower-right).
• From the APPS tab, select Settings.
• From the DEVICE section, select Application manager.
• From the All tab, select Voicemail.
• Select Force stop.
• Select OK.
• From the STORAGE section, select Clear data.
• Select OK.
Please test your voicemail again, after these steps. Let us know if you need anything further.
Follow us on Twitter@VZWSupport
Also you may want to call and check your advance settings on the voicemail system, there is a option to disable notifiaction located there also..
Call Voicemail from phone and login, enter optiions menu and check for voicemail notification (Or Something close to that) because I am using YouMail and cant remeber the correct menus.