There's Eliezer's frequent claim, that for every randomized solution, there's a better deterministic solution that possibly requires more thought.

This doesn't necessarily apply. The usual caveat with the anti-randomization advocation is "except when defeating more intelligent or more privileged enemies". These are the same sort of considerations that the voting systems have to handle. (That is, tactical input from motivated individuals in contrived extreme worst case scenarios.)

That's a very 19th century view. Randomness is a fundamental feature of the world. There is no reason to believe social systems should be any different.