Meu palpite é que com um unsigned int e um varchar 40 (especialmente o varchar!) você tem agora uma chave primária ENORME e está tornando seu arquivo de índice muito grande para caber em qualquer RAM que você tenha para Innodb_buffer_pool. Isso faria com que o InnoDB dependesse do disco para trocar as páginas de índice enquanto pesquisa e isso é um monte de buscas de disco e não muito trabalho da CPU.

Uma coisa que fiz para um problema semelhante foi usar algo entre uma chave verdadeiramente natural e uma chave substituta. Pegaríamos os 2 campos que são realmente únicos (um dos quais também era um varchar) e na camada de aplicação faríamos um hash MD5 de largura fixa e usaríamos ISSO como a chave. Sim, isso significa mais trabalho para o aplicativo, mas gera um arquivo de índice muito menor, pois você não está mais usando um campo de comprimento arbitrário.

OU, você pode simplesmente usar um servidor com toneladas de RAM e ver se isso faz com que o índice caiba na memória, mas eu sempre gosto de fazer 'jogar hardware nele' um último recurso :)