Hmm... I found this while poking around: Google Code Archive - Long-term storage for Google Code Project Hosting.
Softmodem implements a software FSK modem on the arduino using the analog inputs. Stripping it down and specializing it could do the decoding of data from audio without a modem IC. I'll give this a bit of a look while I am waiting for the ICs to arrive.