Selecione a consulta com três onde as condições são lentas, mas a mesma consulta com qualquer combinação de duas das três onde as condições são rápidas

Tente dividir o SQL existente em duas partes e veja quais são os tempos de execução de cada uma. Espero que isso dê a você qual parte é responsável pela lentidão:

parte 1:

SELECT table_1.id
  FROM table_1
  LEFT JOIN table_2
    ON (table_1.id = table_2.id)
 WHERE table_1.col_condition_1 = 0
   AND table_1.col_condition_2 NOT IN (3, 4)
   AND table_2.id is NULL

e parte 2 (observe a junção interna aqui):

SELECT table_1.id
  FROM table_1
  JOIN table_2
    ON (table_1.id = table_2.id)
 WHERE table_1.col_condition_1 = 0
   AND table_1.col_condition_2 NOT IN (3, 4)
   AND table_1.date_col > table_2.date_col

Espero que a parte 2 seja a que demore mais. Nisso, acho que um índice em table_1 e table_2 em date_coll ajudaria.

Eu não acho que o índice composto ajudaria em nada no seu select.

Isso disse que é difícil diagnosticar por que as três condições juntas afetariam tanto o desempenho. Parece estar relacionado à sua distribuição de dados. Não tenho certeza sobre o mySql, mas no Oracle uma coleta de estatísticas nessas tabelas faria a diferença.

Espero que ajude.