I've recently got a new contract on 02 but ive had same trouble ive attempted send texts and get message failed this was about 10 times until i got message sent.
I then hear late on the same day of various friends that the texts id sent hours ago had started to start appearing after hours of them being actually sent

now if my phone tells me a message has failed to send i just try to send again not expecting it take 5 hours to send if its previously told me failed.
Ive had friends on 02 who've had the same problems too with texts failing to send and the actual sim free handset im using i used previously on orange and had no problems at all with orange ive updated software and reset the phone aswell.
I have no problems with calls just texts