I think cheating is only a problem when there is actual competition going on. Public servers in any FPS-game are so random anyway, that only a blatant aimbotter can affect the game negatively. Luckily, these guys are easy to spot and ban by the server admins.
VAC does its job brilliantly. It's a system designed to ban players that can be confirmed to be running a cheating software. It's designed to give no false positives, and so far the Valve's record is clear on that.
I play Team Fortress 2 competitively, and we have our own leagues from which we can ban players according to their Steam IDs. Every league has its own Anti-Cheat admins, who examine the recorded replays of official matches. There is only one player caught cheating in TF2 that has played on the highest level. He also attended LANs where you can't play with your own computer without a noticeable change in his skill level. So you can't really say that he profited that much.
It's just so hard to cheat and stay on top of the competition and not get caught that most people just won't bother. I wouldn't say cheating is a major problem, at least in the TF2 scene.