Correct me if I'm wrong, but you appear to be saying that because observer A thinks he's stationary and observer B likewise thinks he's stationary, that gives rise to a paradox.
But one of the basic differences between Newton and Einstein is that Einstein's maths works for different frames of reference, whereas Newton's is unitary.
And that being the case, there's no paradox.
You also have the problem that Einstein's relativity works all day and all night in reality. You've probably noticed those reports with synchronized clocks, which no longer register exactly the same time after one of them has remained at base while the other has been flown around the world.
And you're no doubt aware that the GPS systems of navigation for pedestrians, cars, boats, planes and spacecraft can't attain the necessary accuracy unless and until they're adjusted to take relativity into account ─ Einstein is needed, Newton won't cut it.
