Cum stai cu fragmentarea indecsilor?
http://technet.microsoft.com/en-us/library/ms189858.aspx
Ruleaza scriptul din exemplul lor si vezi.
In functie de rezultat, poate fi nevoie de "reorganize" sau "rebuild".
M-as uita si la planul de executie al query-urilor lente. In SQL 2008 poti vedea mai repede daca lipseste un index - in partea de sus a planului de executie grafic ("missing index").