But the underlying table changed since. I'm not very familiar with these myself, but it seams to me that the best solution is to keep a session cursor for the user, and these are a lot simpler when you only ever move it forward.
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.
It's slightly different but I don't see why there should be a notable difference in difficulty. You need to somehow represent what you saw so far and act based on that.