Is it possible to paginate posts correctly that are random ordered?

You can use a filter to modify the ORDER BY statement of WP_query.

That way you can manually set the query to use ORDER BY RAND($seed);

Mysql RAND() accepts a seed as an optional argument. Using a seed, it will return the same randomized result set each time.

So you can generate a random number on the first page load then store it in a SESSION variable and use that as the $seed for further paginated requests.

If you are trying to acheive this on your main loop for instance, you could add the following to your functions.php file.

session_start();

add_filter('posts_orderby', 'edit_posts_orderby');

function edit_posts_orderby($orderby_statement) {

    $seed = $_SESSION['seed'];
    if (empty($seed)) {
      $seed = rand();
      $_SESSION['seed'] = $seed;
    }

    $orderby_statement="RAND(".$seed.')';
    return $orderby_statement;
}