Help Mutiple problems with my htc desire with messaging

[Phats]

Right so here's the dillio, I've had my desire for a while now and a few months back it started to not send messages but also not tell me that they hadn't sent until I turned the phone off and then on again. Another problem is that if I have no signal and attempt to send a message I get the little red exclamation mark in the triangle in the notification bar, The phone then sends old messages to random people, the messages had sent the first time round and they can be anything up to weeks old, when I delete my messages it stops it but this is just a major inconvenience. I'm on 3 if that makes any difference, I'm just wondering if anyone's had the same problem or if anyone has a solution