Could it be related with your database? How often do you update statistics on the DB?
I can't link to the Tridion 2009 documentation - because it's offline only - but the process for 2013 and Oracle is documented here and for SQL Server you should just make sure you run exec updatestatssp_updatestats
regularly. I think it didn't change that much from 2009 times.