Well, my experience with CS is that it is fun as long as you can find a good server. And that can be very hard to do some days...
Cheaters do exist in CS, there are lots of them. The degree to which they cheat and how obvious it is varies a lot. I'm not saying everyone's cheating in CS...most people aren't...but it really only takes one or two to ruin a game, out of 10-20 people, and that's not much.
Now, I am good at CS, or at least I was when I played. I know what yoshi is talking about...I often play with headphones, and the sound quality on them is so good I can locate people within a few feet up to about half a map away sometimes (de_dust comes to mind...). Now, to actually be following someone through a wall with your crosshairs...why would you do that? You know where they are by sound, and if not, what business do you have seeing them through a wall? And to actually kill someone in a reasonable number of shots, through a wall, in the general case, is pretty hard to do. Some people who cheat do not do so obviously...things that freelancer pointed out *are* very good examples of this. You can often tell when you watch someone if the way they play is just inconsistent with someone who is not cheating - only checking hiding spots when someone is there, shooting through thin walls over long distances (dust2 doors, anyone? it happens, and it's not always 'skill', sometimes they know you are coming
-- such wonderful reflexes, sometimes they even shoot before you get there, oops).
Playing on the good servers isn't always a solution...maybe it is if you do get lucky and have a good server to always play on, but I normally didn't play CS on such a regular basis. My experience with servers that have admins on them is *NOT* good. Again, this has to do with finding a good server...but in my experience 75% of the servers I play on that have admins will kick me at some point during the game. Not because I do anything wrong, not because I'm being rude to other players. I almost always have a much better score than the other players, and I just end up getting kicked for it. Because of this I have basically just learned to avoid any clan server with members in them...getting kicked because you do well is pretty annoying, ruins the game for me (it is hard enough to find a good server playing a map I like)
So, yeah, CS has cheaters, not everyone but enough to be a major problem, and there isn't an easy solution to it. I don't see how cheat prevention stuff will stop it either (because it won't).