I played competitive level Quake 3/Quake Live for a number of years, during the height of its popularity. I also have friends who play more modern competitive FPS games, such as CS:GO. Even though QL was only a small online scene, the use aimbots, triggerbots, wallhacks, and similar tools was always very common at the competitive level. Quake Live had very limited anti-cheat functionality, so it was never relied upon for proving legitimacy. Despite this, cheaters generally didn't last long in competitive play before being banned. Even if the computer can't unequivocally identify the presence of these tools, skilled players could usually tell the difference. Even if skilled players couldn't tell by watching alone, other contextual factors usually gave hackers away. Such as lack of LAN experience, no history of natural skill progression, etc. I'm aware that this doesn't prove that we caught every hacker, just that we caught many of them.

These cheat tools could apparently be tuned to give extremely subtle advantages to players. Still, over a long enough time period the tool would eventually do something inexplicable enough by normal beahviour to give the player away. I haven't exactly kept up with competitive FPS in years now, however it doesn't seem hard to make aimbots that work well, it seems very difficult though to make ones that consistently appear natural to a trained eye.