I have had this issue also. To the best of my knowledge, it is a problem on your side of the network. The network is recognizing the message as failed. However, the recipient's network does not recognize the message as failed and delivers it as such. I'm not exactly sure why this is but.... Eh.
well i have soft reset so i usually try to do that first but no i haven't done a battery pull, i guess i should since it's gone from me only getting the red x when i have no service to like 4 times today when i've had service.