Is the main problem with cheaters that it's unfair, or that it feels unfair/ruins the experience?

Because if you force all the cheaters to hide well enough to look like "normal" players, no one will know, and the game feel will not be negatively impacted. Outside of the tippy top of competition where money becomes involved, it's kind of irrelevant if the game is technically fair, as long as it feels fair to everyone.