De acordo com esta pergunta , o suporte para tuplas no MySQL não é otimizado. Como @O.Jones escreve em seu comentário, o planejador de consultas no MySQL é uma fera extremamente complexa, e coisas que deveriam trabalho nem sempre se comportam como você poderia esperar.

Acredito que sua segunda consulta seja mais rápida porque a primeira cláusula where dept_id in (101, 103) reduz o espaço de busca para o segundo que usa as tuplas. O otimizador de consulta deve faça isso automagicamente, mas pelo menos no seu exemplo não faz isso.

Eu não acredito no IN cláusula é o problema - é a comparação de tuplas que está varrendo a tabela inteira e não usando os índices disponíveis.