Sua consulta envolve uma tabela com uma coluna datetime ascendente ou datetime2 e um dos parâmetros é datetime ou datetime2, que normalmente está procurando por um valor recente?
Seus comentários sobre o comportamento após a atualização das estatísticas sugerem que você está enfrentando o problema com estatísticas frequentemente desatualizadas que Gail Shaw descreve aqui: link
Como Gail menciona, a resolução mais direta é uma atualização mais frequente das estatísticas. O ideal é segmentar as atualizações mais frequentes das estatísticas que precisam delas apenas - consulte Atualizar estatísticas .
No caso de tabelas muito grandes, um índice filtrado também pode ser útil, dependendo do tamanho da tabela e dos padrões de atualização e leitura.