Perhaps the issue is, partially, structural?
I know some games are super competitive, but what if we generally went back to user hosted (and moderated) lobbies? They clean their own house. Some cheaters would get through, sure, but I feel like there's more social pressure not to cheat among a group of friends vs. raging strangers.