La migliore soluzione di paging con SQL Server 2005?

Per una tabella di quelle dimensioni, utilizzare una Common-Table Expression (CTE) e ROW_NUMBER; usa una piccola funzione per calcolare i record da riportare in base a @PageNumber e @PageSize variabili (o come vuoi chiamarle). Semplice esempio da una delle nostre stored procedure:

-- calculate the record numbers that we need

DECLARE @FirstRow INT, @LastRow INT
SELECT  @FirstRow   = ((@PageNumber - 1) * @PageSize) + 1,
        @LastRow    = ((@PageNumber - 1) * @PageSize) + @PageSize

;
WITH CTE AS
(
    SELECT [Fields]
           , ROW_NUMBER() OVER (ORDER BY [Field] [ASC|DESC]) as RowNumber 
    FROM [Tables]
    WHERE [Conditions, etc]
)
SELECT * 
       -- get the total records so the web layer can work out
       -- how many pages there are
       , (SELECT COUNT(*) FROM CTE) AS TotalRecords
FROM CTE
WHERE RowNumber BETWEEN @FirstRow AND @LastRow
ORDER BY RowNumber ASC