OK so I will share my solution even though it is a little embarrassing. On T-Mobile's visual voicemail you click the message and then have the option to listen or delete. However, if you long click the message you get options pertaining to the contact, not the message. I was long clicking and choosing the delete option thinking that I was deleting the message when really I was deleting the contact.
Yeah, yeah I know....
Sent from my SGH-T989 using Tapatalk