The only solution that seems to work well that I've seen is having very active and good server admins who watch the gameplay and permaban cheaters. Requires a lot of man hours and good UI and info for them to look at, as well as (ideally) the ability to see replays.

That solution only works on servers hosted by players - I've never seen huge game companies that run their own servers (like GTA) have dedicated server admins. I guess they think they can just code cheaters out of their games, but they never can.