The first thing we added was the "rising" page, which used to be reddit's default "new" page. The rising page was a weighted new page. It was a little hacky, but worked for a while. I see they've changed this, which I think may have been a mistake, but I haven't thought about it in forever.
The second thing we did, which worked really well, was to have an up-and-coming link placed at the top of the list on the frontpage. This helped those borderline posts get more visibility. I had a reddit simulator I used to use to test things like this. That space appears to be a subreddit search box for me, so it seems they've moved onto another solution.
Randomness is an interesting idea, though it might be a bit difficult to fit into the way we cached things.
I think the problem that the randomized algorithm solve is not missing good content. It is to give the same chance for equally good content - or at least to minimize the error due to page limit.
to have an up-and-coming link placed at the top of the list on the frontpage
1) either the up-and-coming are a few borderline posts taken in order and then here you'd just extended the front page with a few more posts (ie. it changes nothing)
2) either you'd carefully choosen a heuristic for those posts which is pretty much what is suggested here.
Anyway, thank you for sharing your experience with this problem, it's very interesting.
An other idea would be to fix the content quality and make variable the number of posts in the front page.