It happens, because, when you got back to page 1, the page generated a random results again.
I'm not sure what would be the disadvantages of this, but maybe you could try to cache your db results, then do the paging via PHP.
<?php
if (!isset($_SESSION['results'])) {
$_SESSION['results'] = $all_of_your_rendomized_records;
} else {
$all_of_your_rendomized_records = $_SESSION['results'];
}
// then handle your $all_of_your_rendomized_records's pagination here using php
?>
Im not sure though the disadvantages of this, if this will cosume much memory or something.
But I think it can handle with just 600 records.