Now lets consider the question you did not answer:
What is the comparison between the amount of time a user would stare at a page of 100 records and the time required to retrieve the next or previous 100?
How long does it take to do a typical query on your system?
Personally, I would not mind if, after spending a minute or so scanning 100 records, it took 5 seconds to recover the next 100.
Also, consider this - if there are really that many potential users, suppose user A modifies a record but user B still browses in your cached 1000 records.
Bill