Eu não sei nada sobre Oracle. Mas trabalhei um bom tempo com MySQL e algo que eu via sempre eram queries que não usavam o índice mais importante que era o de data. Isso ocorria quando a query usavam função pra converter datahora pra date,o que invalidava o índice no MySQL.

Tem algo parecido assim no Oracle?

Vi na sua resposta a outro colega que sua query possui TO_DATE, por isso pensei nessa possibilidade.

Além disso, seria possível adicionar um filtro obrigatório no intervalo de datas? Como ele tem uma boa granularidade, isso diminui bastante a quantidade de registros em que os demais filtros (os sem índice) precisam ser executados.

Outra solução que fizemos em um caso foi dividir "fisicamente" a tabela em duas. Registros recentes (no nosso caso 6 meses) em uma, registros anteriores a isso em uma histórico. Dependendo do intervalo filtrado no momento, o sistema decide qual tabela buscar ou faz um union das duas.
Assim focamos nos casos mais comuns e não na exceção.