I could see nothing wrong with the execution plan. Besides, as I understand it, SQL Server 2000 extended many of the performance benefits of stored procedures to all SQL statements by recognising new T-SQL statements against T-SQL statements of existing execution plans (by retaining execution plans for all SQL statements in the procedure cache, not just stored procedure execution plans)
It's a fairly straight forward SELECT statement with sensible table joins, no transactions included or linked servers being referenced within the query and WITH (NOLOCK) table hints applied. The stored procedure was created by dbo and the user has all the necessary permissions.
So my question is this:
What are the likely reasons for a query to take only a few seconds to run but then take several minutes when identical T-SQL is run via a stored procedure?