I'm curious always about this use case.
Does it really make sense for an end user to access a random page?
Why not trying to make the "best results" appearing in the first pages?
Faceted navigation could help to drill down in the results by selecting filters, using a better scoring mechanism which is closer to the use case, adding sorting on various columns... Many things you can do to make the user's life easier IMO.
So what is exactly the use case which would require to access any random document?