pagination and caching

What's the best way to cache a paginated result set with rails and

For example

#posts controller

    def index
    @posts = Rails.cache.fetch('all_posts') do
    Post.paginate(:conditions => ['xx = ?', yy], :include =>
[:author], :page => params[:page], :order => 'created_at D.ESC')

This obviously doesn't work when the params[:page] changes...I can
change the key to "all_posts_#{params[:page]}

But then there could be several possible order (recent, popular, most
voted etc) and there will be a combination of pages and orders..lots
of keys this way.

Problem #2 - It seems when I implement this solution the caches get
written correctly and the page loads fine during the first call do a
paginate action but when I click back on the same page i.e. page1,
with "recent" order, it seems the browser does not even make a call to
the server. I don't see any controller action being called in the
production log??

I am using passenger, REE, memcached, and rails 2.3.5. Firebug shows
no requests being made....

Is there a simples/more graceful way of handling this?