It sure sounds to me like the query could be tuned, but as to the long running stuff, I'd assume contention on resources. While it's running, have you collected wait statistics? Have you watched the server during this period to see if that process is blocked by other resources? Just because not much is happening doesn't mean absolutely nothing is happening, and this sounds like a resource contention issue.