das kann schnell passieren, wenn man in der Konfiguration rumspielt.
Im Telefon *#*#4636#*#* und man kommt zur Telefoneinstellung.
Unter SMSC die Nummer für die O2 SMS Nachrichtenzentrale (wieder) eingeben.
Wer Probleme im UMTS hat bzw. mnur GPRS nutzen kann, sollte dort auch mal schauen.
Links
http://www.android-hilfe.de/motorola-milestone/10448-sms-werden-nicht-verschickt.html
Mehr Infos zu Code auf dem Milestone: http://www.gsmfreeboard.com/showthread.php?t=192253