Your assertion that a game like Starcraft is built such that it makes cheating difficult is unfounded. Because Starcraft players both synchronize the full state of the game, even what's in the fog of war to your opponent means that cheating is trivial. There are some trivial countermeasures here where if the two simulations differ it the two machines will quit over the desynchronization, so you can't just spawn a million units, but you can have full map vision in a game whose rules are tied strongly to the notion of imperfect knowledge of the board.
I've worked anti-cheat (and written cheats) for several games, and there's little you can do in the space of 1-on-1 games to prevent cheating(1), but in the space of 3+ player games the separate simulations can "vote" to remove the player who is cheating (in the desynchronization fashion as above), if you assume there are going to be fewer cheaters in games than legitimate players. Of course if there is any knowledge hidden by the client in its render/UI of the game then a cheater can always recover that data, which is why when you can build a client/server model not transmitting hidden data is the most effective strategy to counter cheating (for example don't transmit entities the player shouldn't be able to see.) This is often difficult, of course, for example if you want footstep sounds to travel through walls in an FPS, but a lot of low-hanging fruit that cheaters would want can be pruned that way.
1: The other (common) approaches are to detect the cheats and punish the cheaters afterwards (Punkbuster, Valve Anti-Cheat, Warden, etc.) or try to lock down the process and make it difficult to write effective cheats (GameGuard, or one trick Blizzard does is attach a second process as a debugger of the game process and IPC validation checks so you can't directly/easily hook into the main process.)
Edit: I now realize you mention hidden data still being recoverable, and desynchronization as a method to combat cheating, I missed that at first but figure I'll leave my post up anyways, even if only to emphasize that seeing the whole map is a very valuable cheat that has taken players easily into the top of the Starcraft ladder (and the top of the Grandmaster rank in Starcraft 2).
