Just to reiterate some of the points from the other thread. Indexes are rebuilt nightly, and fragmentation doesn't seem to be a problem. Statistics are updated automatically, and are also updated manually every night, and don't seem to be out of date. Restarting the service/system didn't seem to have any effect, and I ran a DBCC CHECKTABLE that didn't come up with any errors.