Ok I too had the same issue, actually returned the phone and BOOM it happened again....after spending 3 hours in the store and getting the Samsung rep involved this is what we did....Now I have a sprint phone so not sure about other carriers but with Sprint their is a Voicemail app that comes on the phone. You have to follow these steps....
1. Do a hard reset on phone - be sure to back up everything because it will set the phone back to factory settings
2. Don't set anything up don't click any icons just let the phone boot up
3. Then go to the Voicemail APP and it will have new messages in it to welcome you to that service DELETE THEM
4. Boom the icon goes away and I have successfully restarted my phone and everything and it has stayed away....