Funny
you should mention Google: their policy is to never display more than 1,000 links for a query. Sure, they tell you that there were 2,870,000 hits but they won't show you more than the first 1,000. You might consider copying that idea. Then you just have to read the first 1,000 rows into memory, and your concerns about many calls to the database go away.
Of course this assumes you show the records that are the most important to the user first, like Google does. But you are already doing that, aren't you? You wouldn't make the user click through 20,000 pages in a web application, right?