One choice would be to price out cheaters. Have people pay a one-off fee for access to a premium tier of multiplayer servers. If you cheat, your access is pulled and you've got to go and spend more money to get back in.
Something Awful did this with their forum and it does a pretty good job at keeping spammers and other irritants out.