The packet, whether going to the other guy or coming in to you, is (your ping + his ping + whatever ms the server needs to route it) old, and they come every 250ms, right?
If you get 2 guys with slow (250ms+) connections, yeah, the info they get on each other will be 600ms behind, but it will still be consistantly delayed, right? And if you get 2 guys with fast connections (sub 100), they are playing as close to real-time as is possible- they are able to send and receive that data as fast as the game is able to ask for it. Their info is also consistently delayed, just by a different amount of time. It's not 500ms+ for everyone all the time.
Note that this assumes stable connections. When guys start losing packets or udp or whatever, and the smoothing code tries to predict where they're going for several seconds, and then the next known location is way off some other direction, yeah, you can't avoid **** until their packets start coming consistently again. When that happens though, that's not a fault of the game- you either draw the guy standing still, try to predict his path, or just immediately disco everyone everytime there's a hiccup somewhere.