Why does a query run slower in a Stored Procedure than in the Query window?

As Martin pointed out in the comments, the problem is that the query is using a cached plan which is inappropriate for the parameters given.

The link he provided on Slow in the Application, Fast in SSMS? Understanding Performance Mysteries provided a lot of useful information which lead me to some solutions.

The solution I am currently using is to copy the parameters to local variables in the procedure, which I think makes SQL re-evaluate the execution plan for the query anytime it's run, so it picks the best execution plan for the parameters given instead of using an inappropriate cached plan for the query.

Other solutions which may work are using the OPTIMIZE FOR or RECOMPILE query hints.