A exclusão de dados do InnoDB é a operação mais cara que você pode solicitar. Como você já descobriu, a consulta em si não é o problema - a maioria delas será otimizada para o mesmo plano de execução de qualquer maneira.

Embora possa ser difícil entender por que DELETEs de todos os casos são os mais lentos, há uma explicação bastante simples. InnoDB é um mecanismo de armazenamento transacional. Isso significa que, se sua consulta foi abortada no meio do caminho, todos os registros ainda estariam no lugar como se nada tivesse acontecido. Quando estiver completo, tudo desaparecerá no mesmo instante. Durante o DELETE, outros clientes que se conectam ao servidor verão os registros até que seu DELETE seja concluído.

Para conseguir isso, o InnoDB usa uma técnica chamada MVCC (Multi Version Concurrency Control). O que ele basicamente faz é dar a cada conexão uma visão instantânea de todo o banco de dados como era quando a primeira instrução da transação foi iniciada. Para conseguir isso, cada registro no InnoDB internamente pode ter vários valores - um para cada snapshot. É também por isso que COUNTing no InnoDB leva algum tempo - depende do estado do snapshot que você vê naquele momento.

Para sua transação DELETE, todo e qualquer registro identificado de acordo com suas condições de consulta é marcado para exclusão. Como outros clientes podem estar acessando os dados ao mesmo tempo, ele não pode removê-los imediatamente da tabela, pois eles precisam ver seu respectivo snapshot para garantir a atomicidade da exclusão.

Uma vez que todos os registros tenham sido marcados para exclusão, a transação é confirmada com sucesso. E mesmo assim, eles não podem ser removidos imediatamente das páginas de dados reais, antes que todas as outras transações que funcionaram com um valor de instantâneo antes de sua transação DELETE também tenham terminado.

Então, na verdade, seus 3 minutos não são tão lentos, considerando o fato de que todos os registros precisam ser modificados para prepará-los para remoção de maneira segura. Provavelmente você vai "ouvir" seu disco rígido trabalhando enquanto a instrução é executada. Isso é causado pelo acesso a todas as linhas. Para melhorar o desempenho, você pode tentar aumentar o tamanho do buffer pool do InnoDB para seu servidor e tentar limitar outros acessos ao banco de dados enquanto você DELETE, reduzindo assim também o número de versões históricas que o InnoDB precisa manter por record. Com a memória adicional, o InnoDB pode ler sua tabela (principalmente) na memória e evitar algum tempo de busca de disco.