Tekniken row_number() bör vara snabb. Jag har sett bra resultat för 100 000 rader.
Använder du row_number() som liknar följande:
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
...och har du ett täckande index för kolumnlistan och/eller ett index i kolumnen 'OrderByColumnName'?