¿La mejor solución de paginación con SQL Server 2005?

Para una tabla de ese tamaño, use una expresión de tabla común (CTE) y ROW_NUMBER; use una pequeña función para calcular los registros que se recuperarán en función de @PageNumber y @PageSize variables (o como quieras llamarlas). Ejemplo simple de uno de nuestros procedimientos almacenados:

-- 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