O seu raciocínio está correto, e as suas explicações parecem-me lógicas.

Na primeira frase, a preposição a é dispensável, pois na verdade ela não é regida pelo verbo enganar; ao passo que, na segunda frase, a presença da preposição a é obrigatória, pois ela é exigida pelo verbo agradecer.

A diferença entre «enganá-los» e «agradecer-lhes» é precisamente essa: enganar é seguido do pronome os, que representa o COD (complemento de objeto directo, não introduzido por preposição); agradecer é seguido do pronome lhes, que representa o COI (complemento de objeto indireto, introduzido por a). Contudo, no caso deste último verbo, é possível agradecermos alguma coisa (COD) a alguém (COI). Deste modo, agradecer tanto pode ser seguido do pronome o/a(s) como de lhe(s), como de ambos, numa forma contraída (ex.: «Encontrei ontem o colega que me enviou os apontamentos e agradeci-lhos.»).