this problems almost always ends up by caching all the result pages every 10 minutes using a cron job.
if you don't want to query the database on the 2nd page, and don't care if the data is already old by the time you get to it, then why do you query the database on the 1st page!
just follow ebay, google, yahoo and countless other major sites and cache your result sets. just set up a cron job to do it every 5 minutes or something.