"They could verify those things on other clients..."
But clients are not trustworthy. How do you decide which clients to trust? How long before your 'adversary' discovers your trust methods an replicates them in his client?
"...server which then decides the proper outcome."
This requires processing power. Random sampling is perhaps a possible solution, but if you're overwhelmed with nefarious client activity (50% perhaps) and you're only sampling, say, 10%, still 40% of your gameplay is cheating clients. If you increase your sampling based on finding increases in cheating, you start to overwhelm your server farm.
tl;dr - this is not an easy problem to solve