I’m surprised no one has mentioned this: it’s a numbers game. It only takes a small number of cheaters to reach a critical mass where everyone is encountering them all the time. If only 1% of all players are cheaters and you play games against 10 people in one day, your chance of playing against at least one cheater is about 9.6% on that day. Play 10 players per day for a month (30 days) and your chance of meeting at least one cheater goes up to 95%.
Now consider the effects that cheaters have on the rest of the population: if people get frustrated by cheaters often enough they’re more likely to quit the game. Over time, this can cause the number of non-cheaters to go down, increasing the chances of everyone playing against cheaters. If cheaters are now up to 2% of the population then your chances of meeting at least one in a day (assuming 10 opponents again) rise to 18%.
Conclusion: Over a long enough time span the population of cheaters rises to 100%.