OK, vi har haft liknande problem som detta tidigare.
Sättet vi fixade detta var genom att skapa lokala parametrar inuti SP, så att
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
Vi använder sedan de lokala parametrarna inuti SP snarare än de parametrar som skickades in.
Detta löste vanligtvis problemet för oss.
Vi tror att detta beror på parametersniffning, men har inga bevis, tyvärr... X-)
EDIT:
Ta en titt på Olika tillvägagångssätt för att korrigera SQL Server Parameter Sniffing för några insiktsfulla exempel, förklaringar och korrigeringar.