Try also leaving the parameters and marking the proc for recompile every time it runs. (CREATE PROCEDURE ... WITH RECOMPILE)

Using variables, the optimiser can not make any conclusions about the number of rows that will be affected by any query. I believe it will make a guess at about 1/3 of the table. Hence, you're unlikely to get very good performance but you are guarenteed to never get very bad performance. Essentially, you'll get average performance

Using recompile, you'll get the best possible plan for each run of the procedure at a cost of a slight CPU overhead for the compile.

Give it a try and see what's best for you.

I will recommend that you don't switch parameters for variables unless you know you are having this kind of problem with a particular proc. It's called parameter sniffing and, in general, it's a good thing.