Mi corazonada es que con un int sin firmar y un varchar 40 (¡especialmente el varchar!) ahora tiene una clave principal ENORME y está haciendo que su archivo de índice sea demasiado grande para caber en cualquier RAM que tenga para Innodb_buffer_pool. Esto haría que InnoDB tuviera que depender del disco para intercambiar páginas de índice mientras realiza búsquedas y eso implica MUCHAS búsquedas en disco y no mucho trabajo de CPU.
Una cosa que hice para un problema similar fue usar algo entre una clave verdaderamente natural y una clave sustituta. Tomaríamos los 2 campos que en realidad son únicos (uno de los cuales también era un varchar) y en la capa de aplicación haríamos un hash MD5 de ancho fijo y usaríamos ESO como clave. Sí, significa más trabajo para la aplicación, pero genera un archivo de índice mucho más pequeño, ya que ya no usa un campo de longitud arbitraria.
O bien, podría usar un servidor con toneladas de RAM y ver si eso hace que el índice quepa en la memoria, pero siempre me gusta hacer que 'lanzar hardware' sea el último recurso :)
