I am a senior game admin for a relatively large gaming network.
I tend to find VAC is delayed by a couple of months. Every once and a while a new edition of a cheat will come out and we see an influx and peak of reports and first-hand cases. Some people are really stupid (spinbots, snap-happy, etc). Others are more cunning (trigger-bots, wall-watching). Eventually that edition is detected by VAC and the problem mostly goes away until the next revision is released.
Similar to what KermodeBear described, there is a fairly rigorous review process for demo's before we place a ban. We ensure that it is beyond reasonable doubt - covering off other 'indicators' like game sounds, radar, good tactical awareness, deaths of other players, etc. It can be difficult at times and we err on the side of caution (we would rather a cheater or two go free than ban an innocent player). As KermodeBear eludes to, sometimes the easiest way to initially spot a cheater is when the server suddenly starts sending data about an opposing player as they come within range, and the waller involuntary reacts to the new information. Think when you are playing a game legitimately and a enemy player walks around a corner in front of you - you react automatically in-game by stopping, shifting your aim, shooting, maybe moving to cover. Wallers do this when they suddenly see people though textures, and they react in a similar manner. It sticks out like a sore toe, and definitely prompts us to look for more evidence.
I know that for some games (BF series and an old CSS mod come to mind) there are cheat predictors which capture such events and provide a cheating probability. They can work quite accurately, but we don't use them to 'convict' someone.
Most cheaters actually play very poorly from a tactical and strategic point of view, and can often have very average scores as a result (unless they are aimbotting, which is pretty obvious). And they all get caught eventually, few of them are terribly bright when it comes to taking best advantage of the hacks. Some even forget to turn off the automatic say spam that the cheat sends. It may as well say "BAN ME NOW".
(Actually, the biggest reason for bans on our servers at the moment is derogatory, racist or abusive language. We can't and don't tolerate it much at all. I have no idea why some players cannot go 10 seconds without calling someone else a part of the female anatomy)