Pela descrição do seu problema, parece que você está cheirando parâmetros. Essencialmente, o SQL Server está criando um plano de consulta com base em um conjunto mais antigo de valores de parâmetro que foram passados ​​e que não criam um plano de execução efetivo para a consulta em execução no momento.

Normalmente, resolvo esse problema passando os valores de parâmetro para variáveis ​​locais e usando-os na minha consulta ou usando OPTION (RECOMPILE). No entanto, como você está usando o Hibernate, minha solução usual não é uma opção para você. Pelo que entendi, a melhor opção será usar o Hibernate para executar uma consulta SQL nativa usando prepareStatement() ou createSQLQuery() que, infelizmente, remove alguns dos benefícios de usar o Hibernate.