Sim, o LINQ to SQL funciona com o SQL Server 2000 com uma exceção:você precisa da função ROW_NUMBER(), disponível apenas no SQL Server 2005/2008, para oferecer suporte a paginação eficiente do lado do servidor. Sem ele, as funções de paginação (como Mehrdad aponta) são entregues usando a clássica estratégia Top N - muito ineficiente à medida que você avança cada vez mais em seu conjunto de dados, porque acaba descartando a maioria dos registros selecionados da terceira página.