I've run across this problem several times as well.

I try copying the parameters into local variables, then use the local variables in the WHERE clause.

That almost always fixes the problem.

The two result in very different execution plans, though I've never really understood why.

I'd love to hear what is going on behind the scenes.