Por que minha consulta de várias colunas é drasticamente mais lenta do que as consultas de coluna única correspondentes, mesmo com um índice de várias colunas?

Você criou um índice stop_id, departure_time ? Porque departure_time, stop_id não fará absolutamente nada.

Este é um realmente difícil - tem todas as coisas ruins possíveis para lidar com índices :(

Você tem um intervalo, um OR e um IN não contíguo - não fica pior do que isso.

Experimente stop_id, departure_time e se isso não ajudar, não há muito o que fazer além de mudar para o PostgreSQL.

Você também pode tentar reescrever a consulta como:

SELECT * 
from stop_times 
WHERE ( stop_times.stop_id IN(51511,51509,51508,51510,6,53851,51522,51533)
      AND departure_time BETWEEN '02:41' AND '05:41'
      )
   OR ( stop_times.stop_id IN(51511,51509,51508,51510,6,53851,51522,51533)
      AND departure_time BETWEEN '26:41' AND '29:41' 
      )

ou:

    SELECT * 
    from stop_times 
    WHERE ( stop_times.stop_id IN(51511,51509,51508,51510,6,53851,51522,51533)
          AND departure_time BETWEEN '02:41' AND '05:41'
          )
UNION ALL
    SELECT * 
    from stop_times 
    WHERE ( stop_times.stop_id IN(51511,51509,51508,51510,6,53851,51522,51533)
          AND departure_time BETWEEN '26:41' AND '29:41' 
          )