How about checking to see if any bullets hit the surrounding environment? Even experienced players miss shots because they are human.
That's how I finally spotted it. I thought he was missing all his shots, until I realized that there were no bullet marks on the walls, but there WERE little splashes of alien blood in mid-air. That, and he got credit for all the kills.

The Knuckles video is interesting because, even ignoring the double-lag effect, the aimbot just doesn't seem to "snap" to target the way a classic aimbot does. It may be that the player is more skilled with the bot, and only turns it on in very short spurts.
For me, big markers of an aimbot are instant switching from one target to another, and inhuman tracking when moving quickly around a target. The better aimbotters don't seem to show this very often, possibly because they turn it off and on regularly. Or maybe the bots are just getting better-designed?
I was the one recording those crusaider demos. It's not just at the end that it's noticable. You can see him near the start having trouble keeping it from aiming at teammates. Plus, at times his aim follows the enemies as they go behind walls.
Yeah, targeting his own teammates was how I finally realized it was an aimbot. It's funny, I think he actually shot his teammates more effectively than he shot the aliens. I noticed the wall thing too, but the first time I thought he was pre-aiming using radar. Repeat viewings made a little more sense.