Здравствуйте, Archistratig!
Давненько я тут не появлялся, но было время когда Вы писали:

A>Сортирован — это слишком строгое требование. Вся эта схема работала бы, если бы в SQL существовала конструкция не TOP <n>, а нечто вроде FROM_ROW <m> TO_ROW <n>. Эмулировать ее пратически нереально кроме специальных случаев (вроде вставить результирующую выборку в темповую таблицу с identity и мделать еще один SELECT из нее и прочая неэффективная экзотика).

Когда-то я тоже сталкивался с такой проблеммой. Добрые люди подсказали решение.
К примеру P — номер страницы
N — количество записей на странице
тогда получается следующая картина для 5 страницы из 20 записей

select * from
(select top 20 * from 
(select top 100 * from tbl order by tbl_id) as tmp1
order by tmp1.tbl_id desc) as tmp2
order by tmp2.tbl_id

На выходе получится именно то, что вы и хотели <from 80 to 100>
Возможно этот метод вы отнесете к "неэффективной экзотике", но лично меня этот метод устраивает.
Если-же в нем есть каки-то недостатки — хотелось-бы о них услышать.