RAND accepts a seed in MySQL:
RAND(N)
From the MySQL docs:
RAND(), RAND(N)
Returns a random floating-point value
v in the range 0 <= v < 1.0. If a
constant integer argument N is
specified, it is used as the seed
value, which produces a repeatable
sequence of column values. In the
following example, note that the sequences of values produced by RAND(3) is the same both places where it occurs.
Other databases should have similar functionality.
If you use the SAME seed each time you call RAND, the order will be consistent across requests and you can paginate accordingly.
You can then store the seed in the user's session - so each user will see a set of results unique to them.