Z popisu vašeho problému to zní, jako byste naráželi na sniffování parametrů. SQL Server v podstatě vytváří plán dotazů založený na starší sadě hodnot parametrů, které byly předány a které nevytvářejí efektivní plán provádění pro aktuálně spuštěný dotaz.
Obvykle tento problém řeším předáním hodnot parametrů do lokálních proměnných a jejich použitím v dotazu nebo pomocí OPTION (RECOMPILE). Nicméně, protože používáte Hibernate, moje obvyklé řešení pro vás není volbou. Pokud tomu dobře rozumím, nejlepší možností bude použít Hibernate ke spuštění nativního SQL dotazu pomocí PrepareStatement() nebo createSQLQuery(), což bohužel odstraňuje některé výhody používání Hibernate.