If you’re seeing those posts duplicate across multiple pages in a category, it would seem that your seed may be resetting. I would be interested to know what the output of get_query_var( 'paged' ) is on the category pages you’re visiting.
As an alternative you may be able to store the seed in a cookie and access it on every page load.
Sudo code snippet:
$cookie_name = "myseed"
if(!isset($_COOKIE[$cookie_name])) {
$seed = rand();
setcookie($cookie_name, $seed);
} else {
$seed = $_COOKIE[$cookie_name];
}
// Update ORDER BY clause to use seed
$orderby = 'RAND(' . $seed . ')';