That's why 99% of big-budget multi-player games use predictive netcode with rollback.
http://www.gabrielgambetta.com/fpm1.html
How a game like this exists in this day and age is beyond me...
To see rollback netcode in action, take a look at any FPS or a fighting game with GGPO-style netcode (this is P2P, but the concept is the same).
eg.
http://www.youtube.com/watch?v=q0TZdY9_XHo
One client "thinks" the opponent opponent died so the "KO" sound plays. However, the opponent did actually manage to block in time so the match "rolls back" to a previous state and continues.