Рабочее
Как оказалось, MS SQL Server 2000 плохо оптимизирует исполнение запросов на мультипроцессорных машинах. Когда я насильно заставил его отказаться от распараллеливания коротенького запроса (подняв Minimum query plan threshold с 5 до 500), запрос начал исполняться не за 25-40 секунд, а за 3-4.