I don't know of any free SMS services, you usually buy bulk sms'seses and use an API to send them out.
Whitepages.com has an API that will allow developers to reverse lookup a phone number. It reports the carrier on mobile number, however a lot of the time it's some non-existent-anymore carrier like Powertel or something.
Where I work we've been using http://www.clickatell.com for sending out SMS - it looks like its about 6 or 7 cents a message. They just take http POST requests to send out a message. I don't know if you'll be able to find any good free gateways. We used to send out emails, but found they were unreliable.
Supporting Angus, I can vouch for http://www.clickatell.com. It was used at a company I used to work at. It was a very easy solution to setup and use and worked great. You just need to anticipate how many messages you intend to send out and bulk order messages. They're pretty cheap, overall.
I've used clickatell in the past and found them very good also.
However, You could build your own to get messages VERY cheap. All you need is: a contract which gives loads of (or unlimited) messages; windows mobile phone; and a bit of socket programming.
Write a web service (pass the number and the message) which makes a call to a program on the mobile which sends the message.
I know of at least FTSE100 company which went this route.
I have been doing that with a nokia phone, connected to a linux machine. I have a cron job and a script that would check a database table for new messages and use gnokii to send messages. It works great if the number of sms you are goig to send isn't to big.
Sorry, after re-reading your question i realized this is not the answer your looking for. However this is what i did for my command line program. There's a website where if you put in the telephone number it gives you the carrier. So when i entered my number it screen scraped the website, got the carrier and if the carrier is in my list, i retrieved the email of that carrier
Most companies offer a SMS-to-email kinda thing. For example myphonenumber@verizon.com or something (there's a whole list on wikipedia).
I used that to create my self a little command line application in c# that sends out text messages. However, you don't really get a "reply" and the number is a pre-assigned one from the company.
I think if you want to go the free route, this is your best bet.
You could also get a GSM transmitter and issue AT commands that send sms's. Don't know why you would want to do it this way, but it's another option. This way you won't depend on someone else service
We got fed up with using 'free' sms gateways, very unreliable.
Now we use an sms gateway device called OutboxSMS from Felltech Ltd. It sits on our network and hooks directly into out mobile phone provider using a wireless link from it's built-in transmitter. We needed to buy a SIM card (we got a PAYG with a huge bundle of messages), which is fitted to the OutboxSMS unit. We configured an email account for it on our mail server (MS Exchange), and configured the SMTP/POP3 account on the box.
We use OPManager, this sends alerts by email, which we direct to outboxsms, it parses the message and sends a text message to our ops guys phones when something goes wrong.
We also have some shell scripts which use sendmail to send an email to outboxsms, which again is converted to text messages.
I think this one deserves a new answer. There's a new player in town, it's called Nexmo and features highly competitive prices, even compared to Twilio.