I want to write an app that sends an SMS to users, and when the recipients texts back, I receive that response, including the originating phone number, and my program can react to that response.
I've googled "Interactive SMS" but didn't find anything that was clearly a fit. Has anyone else done this, got any recommendations for a paid service that provides this kind of functionality?
Alternatively, do you have any other recommendations for how to build this service into my app, which will probably be written in C#?
Find an SMS service provider that gives you an API you can use (e.g. an HTTP API). Then read their documentation.
You need to learn about SMPP (short message peer to peer) protocol. Is the protocol usually used to communicate with carrier's SMSC (Short Message Service Center). Here's a blog entry summarizing the actual status of some C# SMPP libraries. If you don't want to use an existing .NET library, you can always write your own. SMPP is not a very complex protocol after all.
An alternative might be attach your application to a cell phone, and if that cell phone provides you with an API, use it to send and receive texts. The problem here is that it won't scale if your application expects to send and receive hundreds of thousands of text messages per day.
Yet another alternative will be to use a CARRIER AGGREGATOR company that provides you with an API for your application. There are some out there, but I don't know if they will be able to offer you a short code and the possibility to receive texts in your application. Depending on the market you are targeting, you should do a little bit of research on how other VAS companies do it over there.
You can use the TextMarks API for this. It's REST-based and super simple to use. So simple that Harvard uses it to teach new students how to use APIs. Docs here.
Messages routed to you from a user are called MO messages (Mobile Originated) and most 3rd party SMS gateways implement simple api's whereby they will simply HTTP post you incoming messages (including the originators msisdn and home network).
For example http://www.clickatell.com/products/two_way.php
Search the site for SMS Gateways for others.
Check SMS Studio - guys have done a lot on that subject and maybe you can use of-the-shelve software or customize it a little to suit your needs.
If not, at least you can find some good keywords for googling.
Anyway, you will have a choice - either go with SMS gateway, or for low volume SMS traffic, you can go with GSM Modem and handle it manually, though it's not recommended.