Server side only anti-cheat is one of the problem domains that I'd really love to work on at some point in my career. This is the type of adversarial arms race that just seems really fun to think long and hard about.
replies(4):
1. Determine minimum human reaction times and limit movement to within those parameters on the client side. (For example a human can't swing their view around [in a fps] in a microsecond so make that impossible on the client) this will require a lot of user testing to get right, get pro players and push their limits.
2. Build a 'unified field theory' for your game world that is aware of the client side constraints as well as limits on character movement, reload times, bullet velocities, etc. Run this [much smaller than the real game] simulation on server.
3. Ban any user who sends input that violates physics.
Now cheating has to at look like high level play instead of someone flying around spinbotting everyone from across the map. Players hopefully don't get as frustrated when playing against cheaters as they assume they are just great players. Great players should be competitive against cheaters as well.