Unusually long time to execute

Hi,
I have a stored procedure which is doing a select joining several tables based on certain conditions.There are two left outer joins and the rest are inner joins. We are using SQL Server 2000. The problem is that this particular procedure is taking unusally long time (10-12 mins) to execute in the production server whereas the same procedure is taking only 40secs to execute in our testing server. We are exploring whether there are proper indexes created (though there are sufficient no of indexes created, we may also consider dropping some index). Additionally i have suggested updating statistics on the involved columns and also to check out for index defragmentation.
Can any thing else should be looked out? What could be the probable reasons and what else should i investigate.
Any suggestion is highly appreciated.
Thanks in advance.

No, data load in testing is much smaller.

Thanx a lot.