The problem here appears to be the banning. If the cheaters are never banned then they will continue to only play with other cheaters, and everyone is happy. And in fact, to a normal player I doubt they care very much if the player is legit and smurfing or if they are not legit and cheating. That player ruins the game they are in.

The ranking system needs to be a better determinate of skill, especially early in a new accounts life, so that they can stop harming normal players games. This might mean changes to the rules of a game to allow this to be done better. The match-maker should take this into account, so that if a player does go up against a player that was far from the skill level that they end up at, it should protect that account from being placed with new players for a time so that they can forget about it.

For the example you choose for Chess, you might force players to do Chess Puzzles before they can queue for their first match. A normal player would then never see any cheaters.