This worked for me >
1) Call your number from another phone and leave a message.
2) Listen to the message, and then delete it. DO NOT exit the messaging menu.
3) Then Press "1" "9" quickly to "Check Erased Messages"
4) Delete the erased message once again.
5) These steps helped the Voice Message Icon to disappear on my SafeLink LG 300G phone.