É legítimo o uso da expressão andar a + infinitivo (ou andar + gerúndio: norma brasileira).

Segundo a Nova Gramática do Português Contemporâneo, de Celso Cunha e Lindley Cintra, diferente das categorias do tempo, do modo e da voz, devemos considerar o aspecto, sendo este uma categoria gramatical que manifesta o ponto de vista do qual o locutor considera a acção expressa pelo verbo.
Ele pode considerá-la concluída, isto é, observada no seu término, no seu resultado; ou pode considerá-la como não-concluída, ou seja, observada na sua duração, na sua repetição. É na circunstância de acção não-concluída que nos surge a expressão andar a + infinitivo.

Existe estar a + infinitivo e outras perífrases formadas com os auxiliares de movimento, estando entre elas o verbo andar. Exs.:

Também podemos ter outros verbos auxiliares de movimento, além de andar: ir, vir, viver, etc.; e  também verbos auxiliares de implicação: continuar, ficar, etc.

Assim, os exemplos apresentados pelo consulente estão correctos.