Have you tried using variables instead of parameters?

Another option would be OPTION RECOMPILE on the statement or WITH RECOMPILE on the procedure. I don't remember exactly when it was fixed, but there was a bug in the OPTION RECOMPILE hint that prevented the hint from working. It should have been fixed in SP2 IIRC. You could give it a try.