[Владимир Максимов]

А вместо переиндексации обновление статистики делать не пробовали?

Т.е. запускаете запрос с Order By и в момент его выполнения (это важно) запускаете обновление статистики. Следующий запрос с Order By должен выполниться быстрее