Encontrei alguns problemas de desempenho usando o método COUNT() OVER(). (Não tenho certeza se foi o servidor, pois demorou 40 segundos para retornar 10 registros e depois não teve nenhum problema.) Essa técnica funcionou em todas as condições sem precisar usar COUNT( ) OVER() e realiza a mesma coisa:
DECLARE
@PageSize INT = 10,
@PageNum INT = 1;
WITH TempResult AS(
SELECT ID, Name
FROM Table
), TempCount AS (
SELECT COUNT(*) AS MaxRows FROM TempResult
)
SELECT *
FROM TempResult, TempCount
ORDER BY TempResult.Name
OFFSET (@PageNum-1)*@PageSize ROWS
FETCH NEXT @PageSize ROWS ONLY