OK, we have had similar issues like this before.
The way we fixed this, was by making local parameters inside the SP, such that
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
We then use the local parameters inside the SP rather than the parameters that was passed in.
This typically fixed the issue for Us.
We believe this to be due to parameter sniffing, but do not have any proof, sorry… X-)
EDIT:
Have a look at Different Approaches to Correct SQL Server Parameter Sniffing for some insightful examples, explanations and fixes.