Could you resolve the issue by introducing an element of stochasticity into the distance players are displaced to avoid collisions?

That way, one player would move right (or left) more than the other player and the collision would still resolve itself.