Some cheats are much more stubborn than others. When a kind of cheat has become rampant in a game or genre, and stopping it doesn't seem to work, lesser designers may just give up and allow their game to become a haven for cheaters and nobody else.
There is also another way. There are several examples of great designers co-opting cheating behavior into their game's mechanics. This has the dual benefits of both putting honest players on an even keel with cheaters, as well as making cheating less beneficial and therefore less tempting to new players.
Natural SelectionNatural Selection was a mod for the original Half-life. It was first released in fall 2002, when wallhacking in the Half-Life engine was at an all-time high. The way NS's developers dealt with this problem was brilliant: They gave both of the factions in the game abilities that allowed them to see enemies through walls.
Aliens could shoot a special form of spit at the humans, which would highlight them as Parasited in the faction's hive sight. They could also purchase an upgrade called Scent of Fear, which caused all injured enemies to show up through walls. Likewise, the humans had a Motion Tracking upgrade, which allowed the humans to see moving aliens as indicators through walls.
These abilities didn't totally neutralize wallhackers. They did still have an advantage, especially in the early moments of the game before humans had managed to upgrade to motion tracking. However, the advantage that cheaters received was much smaller, and once the other gameplay systems had kicked in, it disappeared almost entirely.
EVE OnlineWhile EVE was being developed, the main example of an MMORPG with progression based on character skills rather than level was Ultima Online. In UO, the practice of macroing, or automated skill building, had become rampant. Some players would use macros to train their characters 24 hours a day, becoming much more powerful than non-cheaters and forcing them to either start cheating as well, or to quit the game in frustration.
When EVE's developers designed their skill system, they made what had been cheating in UO officially part of EVE, so they could control it. In EVE, every player trains skills 24 hours a day, even when not playing the game. Being able to predict what skill level every character will have based on how long the character has existed must make balancing that game quite a bit easier.
World of WarcraftA couple of years ago, WoW players were buying in-game currency from goldfarming sites in droves, as well as paying powerleveling services to get their characters up to max level quickly. Blizzard has made several changes to the game since then that have diminished these cheats significantly.
First of all, they introduced daily quests in WoW's first expansion, which are a very easy way for players to make lots of money every day. Players are now more likely to do lots of dailies and send the money to their alts, rather than buy gold online. It's simply too easy to get the money to be worth it in most cases.
WoW's designers also responded to the concerns of players who were unwilling to play the low level content over and over again every time they made a new character. In patch 2.3, leveling speed was greatly increased, making it much easier to get characters to the endgame.
Then, in WoW 3.0, Blizzard introduced the Death Knight hero class, which would allow players to make an alt that started at level 55, further shortening the amount of time spent replaying low level content.
ConclusionIn the first two examples, cheating was introduced by players who wanted a competitive edge. However, in the WoW example, it seems to me that players were really just cheating because the game wasn't giving them what they needed.
Just as pirates may be underservered customers, players may start cheating because they aren't having their needs met. If players in your game are cheating, the most important step is to figure out why they're cheating, which will allow you to implement a countermeasure that actually solves the problem.