mi sono ricordato proprio adesso che con la famiglia AVR XMega (es: ATxmega128a1) avresti potuto farlo poichè possiede una parte hw dedicata chiamata Quadrature Decoder (QDEC)....
Io l'ho provato qualche mese fa e funziona alla grande anche con encoder molto risoluti.