butto giù due pensieri così a ruota libera....
La risoluzione in frequenza di una FFT vale

dove fc è la frequenza di campionamento ed N il numero di campioni su cui si esegue l'algoritmo.
La frequenza dei toni DTMF va da 697 Hz a 1633 Hz, la minima distanza tra due toni è circa 70 Hz, mentre la banda etnro cui il tono è valido è +/- 1.5% come dire da 20 a 50Hz. Vista la distanza direi che ci si potrebbe fare una risoluzione sui 20Hz, così da avere almeno una "fetta" vuota tra due toni "buoni" anche nel worst case delle frequenze più basse.
Per la frequenza di campionamento il minimo di Shannon sarebbe sui 3300 Hz, ma così ci vuole un buon filtro anti alias bello ripido. A me invece piace ridurre al minimo l'hardware , così a spanne, e se non ho sbagliato qualche conto, campionando a 10KHz e con un passabasso del primo ordine si potrebbero avere i prodotti indesiderati sui -10/-15 dB che mi parrebe sufficiente.
Con fc=10KHz e risoluzione 20Hz ci vanno 500, cioè 512 campioni perché è meglio siano una potenza intera di due.
Algoritmi di FFT non ne ho mai fatti in pratica, ma credo che in rete si trovi abbastanza materiale da studiare, ce ne sono vari, da vedere quale sia quello più adatto...comunque tutto (e anche tutto il resto) deve "stare" nei 100us della cadenza di campionamento
da vedere poi è il problema dei troncamenti, se l'aritmetica intera può essere sufficiente o ci vuole il floating point e anche valutare la "profondità" del campione, cioè su quanti bit rappresentare il segnale ma magari per queste cose è più semplice fare una simulazione sul PC con un programmino in C, anzi io prima la farei proprio sul PC per "tradurla" solo alla fine...
E infine last but not least, magari un DSPic è più adatto e hai anche varie librerie già pronte, io "vado" di Atmel, non conosco bene il mondo PIC...
e se invece ti arrendi

c'è
questo