Från beskrivningen av ditt problem låter det som att du stöter på parametersniffning. I huvudsak skapar SQL Server en frågeplan baserad på en äldre uppsättning parametervärden som skickades in och som inte skapar en effektiv exekveringsplan för den aktuella frågan.
Vanligtvis löser jag det här problemet genom att skicka parametervärdena till lokala variabler och använda dem i min fråga eller genom att använda OPTION (RECOMPILE). Men eftersom du använder Hibernate är min vanliga lösning inte ett alternativ för dig. Som jag förstår det kommer det bästa alternativet att vara att använda Hibernate för att köra en inbyggd SQL-fråga med prepareStatement() eller createSQLQuery() som tyvärr tar bort några av fördelarna med att använda Hibernate.