I do not really see what the "problem" is. One can easily define a unique (up to translation) "rotation-free" coordinate system that all observers will agree on

I do not really see what the "problem" is. One can easily define a unique (up to translation) "rotation-free" coordinate system that all observers will agree on, without any reference to "fixed stars" or the rest of the universe. Centrifugal force in a rotating frame is an inevitable consequence of a universe in which conservation of momentum exists. Conservation of momentum is an inevitable consequence (by Noether's theorem) of a universe in which translational symmetry exists (i.e. the laws of motion are not different at some displacement dx). By all observations, all three of those properties hold for appropriate choices of frame. You cannot suppose a universe with both translational symmetry and symmetry under rotational movement; the two are in conflict. If conservation of momentum holds in some coordinate frame, then it will not hold in coordinate frames that are rotating relatively to it. If you suppose a universe where a "rotating" reference frame is the one where conservation of momentum holds, then I would be forced to ask "rotating relative to what, if not an inertial frame?" And the inhabitants of such a universe would still certainly find it meaningful to label that frame as "inertial" and define rotation as relative to it. If you are asking how we tell rotating and non-rotating reference frames apart, the answer is trivial-- non-rotating reference frames obey inertia and rotating frames do not; and there is no ambiguity or disagreement between observers. If you are asking why there exists an inertial reference frame at all, the answer is that this arises from translational symmetry. If you are asking why the universe has chosen a particular coordinate frame to be "non-rotating" over any other, the question seems rather meaningless, because it does not make sense to define rotation except with respect to an inertial frame.