I had this issue a few months ago, and I got rid of it. I can't remember what I did. But now I have the same issue and I can't get that message not sent to come out of my phone and I can't remember what I did but I know I didn't have to have my SIM card deleted or take it to the phone people so if anyone has any ideas please let me know
Welcome to the forums. Have you tried a cache clear for the SMS app you use?