Техниката row_number() трябва да е бърза. Виждал съм добри резултати за 100 000 реда.
Използвате ли row_number() подобно на следното:
SELECT column_list
FROM
(SELECT column_list
ROW_NUMBER() OVER(ORDER BY OrderByColumnName) as RowNum
FROM MyTable m
) as DerivedTableName
WHERE RowNum BETWEEN @startRowIndex AND (@startRowIndex + @maximumRows) - 1
...и имате ли покриващ индекс за column_list и/или индекс за колоната „OrderByColumnName“?