У меня такая же проблема. Сделал следующим образом:

1. Сначала запрос выполняешь целиком. (Плюсы - узнаешь количество возвращенных записей.)
2. Создаешь "временную" таблицу. "Временную" - не в понятиях SQL сервера и еще какой базы, а, например, для каждой активной сессии, т.е. создаешь ее сам. (я так понял, приложение для Web )В этой таблице добавляешь поле IDENTITY, т.е. теперь каждая запись получается пронумерованной.
3. Запихиваешь результат запроса в эту "временную" таблицу.
4. Теперь, когда пользователь захотел получить, например, 30-тую страницу, делаешь запрос к "временной" таблице, используя BETWEEN, где в его параметрах задаешь "размер" выводимой страницы.

Это вкратце. На практике нужно смотреть еще на некоторые вещи.
1. Если, например, количество возвращенных записей меньше определенного числа, то выгоднее не запихивать результат во "временную " таблицу, а каждый раз выполнять полный запрос и ограничивать разбивку на страницы уже на уровне приложения.
2. Если у запроса меняется только порядок сортировки, адресовать его "временной" таблице.
3. Вовремя удалаять эти самые "временные" таблицы.
Вот, вроде вкратце все )) Удачи!