Texts not sending

With both T-Mobile and Three, in the Hartlepool area (North East of the UK) I rarely can send text messages.

They just sit in the outbox and keep trying to resend.

This is on both a the Nokia E61 and the Nokia N93.

Annoying and weird.