If you use MySQL, you can sort all messages that meet random criteria that exceed the criteria, and select the top n.
The actual request will look like
SELECT * FROM posts WHERE votes >= x ORDER BY rand() LIMIT n
Did not test this, but something like this should work in Rails:
Post.all(:conditions => ["votes >= ?", x], :order => "rand()", :limit => n)
source share