Ive never used one. But Olimex makes one with a PIC on board:
http://www.olimex.com/dev/pic-gsm.html

Name: PIC-GSM-1.jpg Views: 1574 Size: 93.4 KB

And for something completely different, works on Satellite:
http://www.sparkfun.com/products/11088 (this is just a connector board for the satellite hardware)
Per message rates seem to be pretty high. But they have something like 15 pre-defined messages that are free to send. So much of status could be sent in the predefined messages (maybe).