Background on the issue
RandomInCategory uses the cl_timestamp field to draw a random page. Because this field is not uniformly distributed it also uses some additional logic to make all entries likely to be drawn but for small- to medium-size categories (think hundred of pages, not tens of thousands) this does not seem to work.
Impacted use cases
On enwiki: The draft review process on en uses Category:Pending AfC submissions to keep track of all the drafts awaiting review, and Special:RandomInCategory to let reviewers pick the next draft to work on. The problem is, the results are very much non-random. See this Village Pump thread for my analysis of the problem.
On Commons: I (DerHexer) use RandomInCategory for some of the categories on Commons of images which I uploaded, bookmarked in my browser. E.g. this, even more obvious in smaller categories like this. Unlike expected, I do not get random images but some very often, sometimes even in the similar order when I click the bookmark, sometimes it opens only subcategories but not files. How can this happen? The function is very helpful and I would very much appreciate to promote this onwiki but this broken I am a bit hesitant.