Stable SQL Server stored procedure unusual drop in performance

I'm experiencing a very strange issue in SQL Server 2005.

Yesterday users reported slowness in a specific part of our database app. I am not sure how pervasive the slowness is - it's definitely not everywhere, as this is the only part of the system reported - but I isolated the relevant stored procedure which used to run in 2-3 seconds and is now consistently running in 50-60 seconds.

It's a complex query -- multiple layers of subqueries. It returns only 42 rows in 16 columns.

The query looks like this:

select col1,2,3,4,5,...
from 
( select .... ) t
ORDER BY col1

I started picking apart the query to find out what was slow and found that removing the final ORDER BY clause brought the performance back in line.

This is highly mysterious. I could not replicate the problem on our DEV server. It's only 42 rows so the order by clause should be inconsequential. Execution plans are identical w/ and without the order by, and on the two servers.

Any brainstorming about what could have changed on our production server would be much appreciated!