I don't think the core of the idea is literal randomness injection. Compare for a moment high precision measuring devices. Any decent measuring device comes with a manual describing the tolerances of the device, the error rate, the expected skew caused by error and so on. They may be highly accurate, and very precise, but they don't claim 100% accuracy. Yet, ideally, this should be a simple task -- the math says if we do X to make the device, there is only one solution and the device is perfect. We take pains with these devices to construct them perfectly, but errors still slip in - and we acknowledge it. To counter these errors we do statistical analysis on the machines' output, we scrutinize anomalous readings and discard or normalize data within the error range and otherwise account for errors.

Look now at the Bush/Gore election cited above, in light of this. A vote is simply a measurement of the people's desire for leader X or leader Y. This measurement is taken via a tool called the ballot. The ballot is for some reason taken as an ideal measuring device - for some reason we think it is a perfect tool of measurement. Yet, a huge chunk of the debate and contention of the scenario came out of problems with the ballot itself -- hanging chad, butterfly ballot confusion, and so on, are all measurement issues. At some point, we should have said "look this is just too close to call with our ballot measuring system, other measures or means should be used to determine the outcome".

The same is true of tests, they are an imperfect measuring system we are trying to treat as idea; so are many other systems you allude to.

The core idea here, is to stop treating our measurements as some sort of ideal measurement and instead look at alternate measures and methods once you get within the error range of the original measuring device -- at this point you are in the realm of "luck" anyway, because there are other unaccounted factors affecting the measurement anyway. Further, it has no more effect on cheating than treating an imperfect measure as ideal -- cheaters in both cases attempt to exploit unnoticable issues in the measurement. Statistical cheating detection already considers this sort of thing anyway, if the statsticians are any good.

As for the social situation you present -- this is a trickier problem, but I suspect a large portion of it could go away once proper understanding is given to people. A lot of the "unfair" complaints are essentially based around "the measure is perfect, so if I can tweak the value measured of my by a small bit, it has some fundamental implication". Essentially we need to train people on the difference between platonic ideals and the realities of the scenario. Then instead of complaining over obscure minutia, energy can be focused on either bettering the overall situation, or bettering the measurement.

As to your final point: ignoring the imperfectness and pretending it is perfect does not really change the gaming problem, in fact it adds to it, because when you treat the imperfect as perfect, you must have lots of complicated rules, which also allow for crazy gaming. Instead effort could be better spent on gaming detection or simple administrator investigation/oversight.