I did a little research this afternoon. If you're willing, you can get a c168i for $15 or so. Since it's a GSM phone, it'll work on tmobile, and their prepaid is reasonable @ 5¢/10¢ to receive/send sms. I think you have to add money to the account ever 90 days or so, but other than there aren't any costs. Unlike AT&T, tmobile doesn't push back a message every time you send something from the phone. I have a project where I'm considering something like this myself, and I'm kind of leaning on going with an old phone rather than trying to find a new one. Not the best solution, but one that should work.
This place carries the phone for $14.95 and no shipping FWIW:
http://www.dotcells.com/Motorola/ATT-Cingular/Motorola-C168i-ATT-Cingular-p6062036.html