However, if the player is genuinely doing a least-recently-played rather than a random, then I would think that would be a bug.

Aha. I've confirmed from the inside that the player is doing a least-recently-played there, so it explains the behavior you're seeing. There's discussions going on about how best to prevent the undesired results you were seeing.