random list but unique view of post type in WordPress

I am working on a site for a realtor company. They have a page called agents, where list of all agents are shown. the agents are added with a custom post type in the site. The client's requirement is that, on every visit of this page, the agents list should be shown randomly. We have used orderby and it's showing the agent list randomly.

$wp_query->query('showposts=8&post_type=agent&orderby=rand'.'&paged='.$paged);

But the problem is it keeps randomizing the agent list even in paginated pages.

Clarification: Let's say there are 8 agents and we show 2 agents in every page. It shows the user that there is a pagination and so we get 4 pages.

Suppose these agents' names are 1, 2, 3, 4, 5, 6, 7, 8. what we need is, for a visitor the list will be randomized. Let's say, when I visit, the randomization will be 1, 3, 2, 5, 4, 7, 6, 8. In first page 1 & 3 will be visible, in second page 2 & 5 will be visible and so on...

But what WordPress orderby does is, it randomizes it even in paginated pages also. If we consider it with the example above. they may show 1,3 in first page, 2, 4 is second page, 1, 7 in 3rd page and 6, 8 in fourth page. So, there is always chance that a post will always be left out like the way 7 is left out in my example.

Now, how can we customize it so that it ensures that post orders will be random and no post will be shown multiple time for a user's visit.

Thanks.