Perché la mia query a più colonne è notevolmente più lenta delle corrispondenti query a colonna singola, anche con un indice a più colonne?

Hai creato un indice stop_id, departure_time ? Perché departure_time, stop_id non farà assolutamente nulla.

Questo è un davvero difficile - ha tutte le possibili cose negative per gestire gli indici :(

Hai un intervallo, un OR e un IN non contiguo - non c'è niente di peggio.

Prova stop_id, departure_time e se non aiuta, non c'è molto che tu possa fare se non passare a PostgreSQL.

Puoi anche provare a riscrivere la query come:

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' 
      ) 

oppure:

    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' 
          )