also, if you are running on an old server with I/O bottlenecks, are you running SQL2008. An earlier versin may affect the answer.

Its not an area I am familiar with, but would partitioning the table help him out here?