Não há necessidade de 'reconstruir' um índice. Eles são sempre mantidos atualizados. Talvez ele estivesse se referindo à reconstrução da mesa. Dependendo de seus padrões de uso e esquema, você pode obter páginas fragmentadas no InnoDB e acho que no MyISAM também. A reconstrução da tabela pode melhorar o desempenho eliminando a fragmentação de seus dados no disco. Eu não uso tabelas MyISAM regularmente, mas acredito que seja recomendado executar 'OPTIMIZE TABLE' com certos padrões de uso. Veja os documentos do MySQL em OPTIMIZE TABLE para algumas boas informações sobre MyISAM e InnoDB.

Não estou tão familiarizado com os meandros do MyISAM, mas com o InnoDB é verdade que as estatísticas podem ficar desatualizadas. O banco de dados mantém estatísticas estimadas sobre como seus dados são distribuídos para um determinado índice, e é possível que eles fiquem desatualizados, mas o MySQL/InnoDB tem algumas funcionalidades internas para tentar manter as estatísticas atualizadas. Normalmente você não precisa se preocupar com isso.

Portanto, se você estiver usando o InnoDB, a resposta é não, você normalmente não precisa fazer nada ativamente para manter seus índices com bom desempenho. Não tenho tanta certeza com o MyISAM, acho mais comum precisar otimizar essas tabelas regularmente.