Cita: el EXPLAIN no me da nada raro como para preocuparme
¿Podrías, por favor, postearnos el resultado del EXPLAIN?
Cita: entonces queres decir que al reindexar tablas MyISAM no asegura la optimizacion como las innoDB?
Reindexar tablas MyISAM no tiene NINGUN efecto sobre las InnoDB. Son motores de tablas completamente diferentes.
Y además yo no estoy hablando de reindexar las tablas, sino de crear índices sobre lesas columnas.
Cita: seria conveniente pasar de un tipo de tabla a otro?
Eso es una decisión de diseño. Dependera de lo útil que te resulte, pero con la poca información que sobre las tablas nos das... la verdad no tenemos mucho para decirte al respecto.
Lo que si, ten en cuenta que al pasar de un o a otro tipo, y poner verdaderas FK en esas columnas, pueden aparecer todos los errores de datos que existan.. lo que te llevará tiempo depurar.