A few years ago I wrote a whole lot of telecom tone generation and detection stuff in PIC assembler, with the aim of getting 2 PICs to talk over the phoneline using a software generated V23 modem.
I wanted a cheap way of getting trivial data from remote sensors, and before Pachube, and "always on" broadband, the standard PSTN phone line seemed an attractive possibility.
Over the course of the project (and several years) I got the following building blocks to work:
DTMF decoding in firmware
V23 modem sending
V23 modem reception
Auto answer on recognised Caller ID
The whole lot is documented on the Yahoo Group "rat_ring"
It's not just the firmware, you also need to know how to connect a micro safely and cheaply to the incoming phone line - and the rat_ring has a 40 page tutorial describing the interfacing techniques.
My Called ID interface was just 4 diodes in a bridge and a single NPN transistor to amplify the Caller ID signal and get it into the digital input pin of the PIC. I like minimalist designs!
So my suggestion is that anything that can be done on a PIC can be done on an AVR, and most things that are done in assembler can be done in C.
Somewhere I have a firmware Caller ID decode program written in AVR C.
With a little bit of encouragement (and assistance with C) , I could be persuaded to get this stuff to run on an Arduino.
The other possibility is to graft on a cheap V23/Bell 202 modem chip onto the Arduino. Have a look at the CMX86X series from Consumer Microcircuits Ltd, (CML). These connect via a serial bus and have DTMF send receive, and V23/Bell 202 send receive all in the one cheap device.