Pagination/Page Navigation and post randomization

I need to display a list of randomized posts on a paginated page. In other words, I have 10 posts per page, 15 posts and they need to appear randomized across those two paginated pages.

There’s been a handful of posts on the forums (and a little activity elsewhere) about this issue but no good solution. Does anyone have an idea how it could be done?

http://wordpress.org/support/topic/problem-with-the-page-navigation-and-randomizing-posts

http://wordpress.org/support/topic/random-posts-over-multiple-pages

http://wordpress.org/support/topic/random-posts-on-several-different-pages-pagination-works-but-repeats-posts

Thanks!!!