I have an sproc in SQL Server 2008. It basically builds a string, and then runs the query using EXEC():

SELECT * FROM [dbo].[StaffRequestExtInfo] WITH(nolock,readuncommitted)
WHERE [NoteDt] < @EndDt 
AND [NoteTypeCode] = @RequestTypeO 
AND ([FNoteDt] >= @StartDt AND [FNoteDt] <= @EndDt) 
AND [FStaffID] = @StaffID 
AND [FNoteTypeCode]<>@RequestTypeC 
ORDER BY [LocName] ASC,[NoteID] ASC,[CNoteDt] ASC

All but @RequestTypeO and @RequestTypeF are passed in as sproc parameters. The other two are built from a parameter into local variables. Normally, the query runs under one second. However, for one particular value of @StaffID, the execution plan is different and about 30x slower. In either case, the amount of data returned is generally the same, but execution time goes way up.

I tried to recompile the sproc. I also tried to "copy" @StaffID into a local @LocalStaffID. Neither approach made any difference.

Any ideas?