It was related to client falling way behind the server and interpolation performing wrongly as a result.
I also deployed a massive optimization (or rather a fix) to the netcode that should improve performance when the network conditions are good - there was a bug that caused the client to resimulate the world every frame even though it was not necessary whenever it predicted the world correctly.