Yes, the use of state machines seems to be required. I was wondering about more precise ideas about making it not to slow, but flexible. The problems I had were mainly to combine absolute time (speed of the combo) and precedence an elegant way, and to limite the use of saved pad datas to the minimum needed.
Do you know some articles about the subject or, maybe better, free implementations ?