How Lag Compensation Works
This works because the server decides what bullets do, not your client and not their client.
The server does this by knowing how good (or bad) your ping is at any given moment and can use that to calculate player's positions at different points in time. Different games "rewind" these positions in different ways, but the general principle is maintaining a certain window of position data and when you shoot a hitscan gun (these are ones like TF2's heavy's minigun, scout's shotgun, etc: basically anything that uses fast moving bullets) the server looks at where players were Xms ago (based on YOUR ping) and then performs the hitscan (raycast) and applies damage as required.
Slow bullets are different. Slow bullets are tracked as entities. Types of slow bullets in TF2 would be grenades, rockets, and flamethrower particles. Each of these is tracked on the server by the server and lag compensation is only applied once (to see how far away from the shooting player they need to have moved before entering the standard update loop).
The reason you see the bullet "miss" but damage the player anyway has to do with what YOUR client knows about the positions of objects in the game and the interpolation your client does to make things move slowly. As players only care that damage is dealt and how common ping, lag, and lag compensation as known mechanics are these days player accept these sorts of inconsistencies when dealing with high-latency situations that there's not a real problem here. Rather, the problem is the fact that the lag compensation systems are not good enough in edge case scenarios or can offer an advantage to players who install a lightswitch in their eithernet cable...artificially introducing lag on demand that lets them have 3 seconds where their client is (effectively) in charge because TF2 gives a bias towards the shooter with some weapons (like the sniper rifle).
And as every programmer should know:
The client is a lying, cheating bastard.