Verifique a configuração dos dois motores. É possível que a configuração do seu mecanismo InnoDB seja mais eficiente para suas pesquisas do que a forma como você configurou o MyISAM.

Um valor de configuração de chave é innodb_buffer_pool_size, que é onde o InnoDB armazena dados em cache (e índices, mas você não tem nenhum índice).