OK, abbiamo già avuto problemi simili come questo.
Il modo in cui abbiamo risolto questo problema è stato creare parametri locali all'interno dell'SP, in modo tale che
DECLARE @LOCAL_Contract_ID int,
@LOCAL_dt_From smalldatetime,
@LOCAL_dt_To smalldatetime,
@LOCAL_Last_Run_Date datetime
SELECT @LOCAL_Contract_ID = @Contract_ID,
@LOCAL_dt_From = @dt_From,
@LOCAL_dt_To = @dt_To,
@LOCAL_Last_Run_Date = @Last_Run_Date
Utilizziamo quindi i parametri locali all'interno dell'SP anziché i parametri passati.
Questo in genere risolveva il problema per noi.
Riteniamo che ciò sia dovuto allo sniffing dei parametri, ma non abbiamo alcuna prova, mi dispiace... X-)
MODIFICA:
Dai un'occhiata a Approcci diversi per correggere lo sniffing dei parametri di SQL Server per alcuni esempi, spiegazioni e correzioni approfonditi.