Different Parameter Value Results In Slow Query

Question

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?

UPDATE: Tried to drop specific plans using:

DECLARE @ph VARBINARY(64), @pt VARCHAR(128), @sql VARCHAR(1024)

DECLARE cur CURSOR FAST_FORWARD FOR
  SELECT p.plan_handle
  FROM sys.[dm_exec_cached_plans] p
  CROSS APPLY sys.dm_exec_sql_text(p.plan_handle) t
  WHERE t.text LIKE N'%cms_selectStaffRequests%'

OPEN cur
FETCH NEXT FROM cur INTO @ph

WHILE @@FETCH_STATUS = 0
BEGIN
  SELECT @pt = master.dbo.fn_varbintohexstr(@ph)
  PRINT 'DBCC FREEPROCCACHE(' + @pt + ')'
  SET @sql = 'DBCC FREEPROCCACHE(' + @pt + ')'
  EXEC(@sql)
  FETCH NEXT FROM cur INTO @ph
END

CLOSE cur
DEALLOCATE cur

Either the wrong plans were dropped, or the same plans ended up being recreated, but it had no effect.

Answer 1

Doing an UPDATE STATISTICS ... WITH FULLSCAN on the main base table in the query resulted in the "slow" value not being associated with a slow plan.