We figured out why this starts to happen. Basically if a vehicle is on the map with less than 3 wheels, it counts as a "non-entity" or whatever.
That then causes the whole server to go into a state of "desync". Basically until the server restarts again you will have a bunch of different issues as described in this thread.

So we've got "no collision damage" configured for all vehicles, so before 1.19 when I hit a tree like this it would just bounce off and I would continue as normal.