Playing to Strengths
Humans have several advantages: They are better at strategy and better at pattern recognition. There are several ways to design a game that plays to these benefits.
Imagine a first-person shooter game in which the players would be invisible. Rather than the server sending each player the location of the others, it would send slightly blurred images of the walls. Ideally, the patterns on the walls should move as well, preventing a computer from simply comparing the changes between frames.
A human player could look at the walls and see which bits changed in a different pattern to the backdrop. This human could quickly see their invisible opponents and shoot them. A computer player would have more difficulty.
This kind of game would require a little more bandwidth than current games, but there are some optimizations that could be applied to reduce the load.
Another thing to do is automate as much as possible. Give individual units intelligence. If the player is controlling an army, make each unit react tactically in the same way that they would if AI-controlled. The human could concentrate on strategy, eliminating the parallel micromanagement advantage that a computer has.
There are a lot of different ways in which a game can be designed to minimize the potential for cheating. Rather than concentrating on spotting cheat programs, it is far better to produce a game that is, by design, biased towards human players. The result is less effort making a game cheat-proof and a more enjoyable game.