Well, there are yet other options, depending on the amount of data you need to transfer back and forth to the server.
Instead of sms, for short amount of data you could try to implement an Asterisk PBX, whith your mobile calling your server and then sending other DTMF digits as your data, which would be interpreted by your Asterisk PBX (like an interactive phone audio menu from your cable company). Asterisk is GPL open-source.
Another option (an expensive one and with heavy work to do), would be to generate an audio signal encoded with your data content, and dial a phone number linked with an attached fax/modem pci board on a server, sending that audio like a call. It would'nt need to be a long call, as you could fit lots of data in a short bursts of audio stream.
Your server could check that data by acessing the content on the receiving end. Simply recording the call from the attached fax/modem pci board, or you could use an Asterisk PBX server on a local computer to save the audio file and then process by your server software.
Anyway, you would need to create a new protocol and data encoding type, like you mentioned "machine-readable encoding".
So, for the data types you could just save a lot of short audio files on your mobile and play them as your datatypes, but it would be easier to just go for the DTMF already mentioned above. Or you could encode like this: get the sound spectrum allowed to use through the voice call (Wideband/Narrowband), and divide it by the amount of single characters or chunks needed (take a look at how to encode in base64, to have some ideas). Then create a function to just encode your data as a short audio stream (read about PCM encoding and also read more about Fast Fourier transforms, if you want to complicate (but speed up) even further.
Create a simple protocol like this: first audio packet is a sequence of tones that makes a request, authenticates, and waits for acknowledgement response from the server (which could be just by not dropping the call 1 second after that). The 2nd audio packet is the size of the first frame of data, then the 3d audio packet onwards is the data itself with the size shown before. And so on. Have a look at the ftp protocol description for simplicity. Then you need to refine it so that the time of every packet above is the least possible while mantaining confiability.
For costs saving on voice calling, you could also explore phone number options, like Google Voice, Skype or any Voip service.