Row_number()-teknikken burde være hurtig. Jeg har set gode resultater for 100.000 rækker.
Bruger du row_number() svarende til følgende:
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
...og har du et dækkende indeks for kolonnelisten og/eller et indeks i kolonnen 'OrderByColumnName'?