I'm an expert in a neighboring field: numerical optimization. I've seen lots of evidence for Jaynes's impression that for any algorithm that uses randomness, one can find a deterministic technique (which takes thought) that accomplishes that goal better. (For example, comparing genetic algorithms, simulated annealing, and tabu search, the last has an deterministic memory mechanism that gives it the ability to do both diversification and intensification, with much more control than either of the other two.) Random methods are employed frequently because to do otherwise would require thought.

As for the debate, to me it looks like it was over terminology. To illustrate, let me label three different cases: the 'benign' case, where the environment is assumed to be dumb (i.e. maxent priors are reasonable), the 'adversary' case, where the environment is assumed to be an agent that knows your algorithm but not your private source of randomness, and the 'omega' case, where the environment is assumed to be an agent that knows your algorithm and your private source of randomness.*

Eliezer thinks the phrase 'worst case analysis' should refer to the 'omega' case. Scott thinks that the 'adversary' case is worth doing theoretical analysis on. The first is a preference that I agree with,** the second seems reasonable. I think Silas did a good job of summarizing the power that randomness does have:

Which is why I summarize Eliezer_Yudkowsky's position as: "Randomness is like poison. Yes, it can benefit you, but only if you use it on others."

*There's also a subtlety about solving the problem 'with high probability.' For a deterministic algorithm to have a chance at doing that, it needs to be the benign case- otherwise, the adversary decides that you fail if you left them any opening. For a randomized algorithm, the benign and adversary cases are equivalent.

**One of the things that Scott linked--when Monte Carlo goes wrong--is something that shows up a lot, and there's a whole industry built around generating random numbers. For any randomized algorithm, the real worst case is that you've got a PRNG that hates you, unless you've paid to get your bits from a source that's genuinely random, and if omega was the case that came to mind when people said 'worst case,' rather than adversary, this would have been more obvious. (vN got it, unsurprisingly, but it's not clear that the median CS researcher did until they noticed the explosions.)