Yeah, very true. I have an idea about how to detect cheaters, if you want to hear about it. Basically, I think the way to detect whether someone is cheating in an online game is by applying spam filtering techniques.
First consider that every server-side game state (like a player's position in the game world) can be considered a statistic. So for example, a history of a player's speed at points in time would have certain maximums. (i.e. "players don't usually move at 500MPH. And if they do, they only do so for very short periods of time.")
Therefore, by definition, a cheater is a player whose statistics are significantly different from the norm. A speedhacker could be detected because his max speed would become way above the "typical" maximum player speed over a significant amount of time (like, he begins to run at 500MPH for 2 solid minutes). So we can then boil the problem of detecting cheaters down to evaluating probabilities (which is the same way spam email is identified).
This type of system would also handle the case where there's a game bug that accidentally causes players to run fast -- the system won't accidentally boot everyone, because everyone is now running fast, so therefore that fast movement speed becomes "normal". Now let me point out that the very same thing could be accomplished much more simply by just writing code to boot players when their speed exceeds a certain hard-coded maximum global speed, then being very careful to not introduce a superacceleration bug. However, that's special-case code, which should typically be avoided. It also doesn't take into consideration that a player's speed could legally be significantly accelerated for a short period of time by physics, for example, or for a number of other reasons. The idea is to analyze samples of a number of different game statistics, then boot any player whose maximum statistic value significantly exceeds the normal maximum value over a significant amount of time.
This type of system would prevent a situation where a cheater discovers how to manipulate the timing variables in packets, then tricks the server into thinking he's moving faster than he actually should be. (I believe Counter-Strike: Source is still affected by that particular speedhack problem.) We would also be able to detect and ban players using aimbots, because it is very statistically significant for a player to murder 20 opponents in 10 seconds, for example.
So if people modify the client to cheat, the server will identify and ban them. Godda love probabilities and statistics.