IMO "pages of search results" is one of the problems where the closer you look, the more potential problems and inconsistencies you see until you realize it's a leaky abstraction, and sometimes it gets too leaky.
We want visitors to imagine that we just plopped a binder of sorted results down in front of them for their page-by-page perusal, but the suggests permanence and invariants we don't want to provide (because it's harder.) For example, the assurance that page 2 will always have the same items on it unless they "search again", and the last item on page 2 will not not duplicate itself on the top of page 3 as they page forward.
By way of contrast, imagine a system where a result-set was not just a UI metaphor, but real domain concept. Do a search, and you get a Result which is a limited-size listing generated at time X for user Y and will be cached for Z.
