arcade cheaters

so I know it exists and happens...
but how do you guys detect a cheater when you only SUSPECT he is cheating?

he is doing in a way that is not totally obvious...but if I had to bet or guess, I'd say I'm like 90% sure he is cheating.....certainly on a few games (3x other score, first try, and against players I KNOW very good and have played a lot), but others, again, very close. and then again, there are sometimes guys that just "know the trick" to a game (without external cheat methods).

-is there a way to check for sure?

-do I ban him?
-do I warn him?
-prune all scores?
-prune some of the scores (one's I'm sure)?

any suggestions would be appreciated. everyone knows how these guys can kill an entire arcade.

do any of you use post minimums before people can play? I have a bunch of people that basically only register or only play in the arcade +_+.