FPS is one of those subjective issues where there seems to be a lot more "I don't like X so you are daft for suggesting someone might" then hard facts.
It really depends on how the game is built. For lack of a better way to describe it, some games actually have multiple CPU frames per GPU frame. You can fire in the frame that doesn't get rendered - you just won't see it. (or perhaps more aptly, games can have more input frames, so even though you're running at 20fps, you can still have 100fps accuracy, if you can guess where to shoot)
As an example, I tested this in L4D1 when my old GPU was acting up. I had to downgrade from an 8800 to an 8300. My FPS dropped from ~60 to ~15-20. Frequently I'd move my crosshair, click where I thought my zombie was, and when the next frame rendered it was on the other side of a corpse flying through the air.
Of course, L4D2 messed this up by having zombies randomly change directions and speeds, making it much harder to predict where they'll be. Plus the hit detection is just plain funky - at 60fps, I can fire to the left of something running right, and kill it - but it doesn't work nearly as well at low framerates.