Use Query Analyzer to look at the execution plan for the statement when you pass in a variable and when you provide the value direct. If you have multiple indexes...

Are you calling the SP from Query Analyzer, or running the code of the SP in QA?

If it's the latter, are you declaring all the variables passed into the...