I've had this same issue come up with my Droid X, and eventually, I just had to Factory Reset and then had tech support clear out all text messages. Finally they were gone.
What I learned? I learned when I get a "message not sent" notification, go to the notification. Click the note and let it take me to the message. By letting the system go through the motions to "resend message", I've been able to keep this issue from happening, ever again, it's been about a month since this happened. Now if the message still won't go through a second time, I'll delete the message and move along.