You can check GSM modules from siemens ..
GSM/GPS XT75 QB GSM/GPRS-12/EDGE-10/GPS, TCP/IP, Java, 80-pin, UFL (150$)
GSM MC35iT DB GSM/GPRS-8 Terminal, DB9, FME (150$)
GSM TC65T QB GSM/GPRS-12 Terminal, DB9, 24-pin M-N-L, SMA (190$)
http://www.tdc.co.uk/datasite/wireless/gsm/_data/datasheet_xt75_175004.pdf
**broken link removed**
**broken link removed**
TC65 support SPI/I2C bus as well as rs232 .. all of them support rs232 .. pretty easy to use, especially for SMS .. they also support GPRS/EDGE (not all support edge, all support gprs) so you can even send data via network .. I saw only MC35iT with my own eyes and it is very small so you can put it anywhere
I used some old nokia 5110 but lost the darn datasheet with AT set to send sms .. but as I had no need for it for some time I was not really looking... The nokia AT set should be easy to find and as phone use ttl rx/tx .. you do not even need max232 .. you can directly connect your uC rs232 to the phone ..
EDIT: very usefull link:
EDIT: another one: **broken link removed**