Random posts on several different pages – pagination works but repeats posts

We have created a site where members can recommend things like favourite books, movie, songs, etc. For this problem I will use the Movies page as an example.

The “Movies” page is ultimately a custom page template that asks wordpress to display a random list of ALL posts that have been given the category “movies” (category 31). It displays the title of these movies in random order using the code below.

‘<?php $rand = new WP_Query(“cat=31&showposts=-1&orderby=rand”); while($rand->have_posts()) : $rand->the_post();?>” rel=”bookmark” title=”Permanent Link to <?php the_title_attribute(); ?>”><?php the_title(); ?>
<?php endwhile; ?>’

Problem is the list is getting rather long and I would like to split it up into two or more pages of about 10 movies each. To achieve this, I have used the code below.

‘<?php $page = (get_query_var(‘paged’)) ? get_query_var(‘paged’) : 1; query_posts(“cat=31&orderby=rand&showposts=10&paged=$page”); while ( have_posts() ) : the_post() ?>” rel=”bookmark” title=”Permanent Link to <?php the_title_attribute(); ?>”><?php the_title(); ?>
<?php endwhile; ?>’

But there is a problem because although it splits up the data into pages of 10 posts each (paginates), it fails to include a new set of 10 posts on page 2 and so forth. In other words, because it is listing things in a random order, it just goes out and gets another 10 random posts (or in this case movie titles). As a result, we have some repeated movie title posts instead of a new set of 10 random movie titles on page 2, etc.

My question is – what can I add to this code to get wordpress to “remember” which random 10 posts it included on page 1, and then have it get a new set of 10 posts to put on pages 2, 3, etc. until all posts are displayed. I would like there to be only one occurrence of a post per page when sorted randomly in sets of 10.