Charging money and banning at the payment provider level can be quite effective. It isn't a perfect answer but it cuts out gigantic chunks of the problem space.

I'll take a ~99% cheat-free experience over not having any improvement at all.