The POR is in fact a meta law ie a law about laws. Physics, in general, would be in deep do do if it failed in a drastic way. What is more likely to happen is it may fail in some 'realm' way beyond everyday experience in which case, like so many things in physics, its simply something applicable only to a well defined 'realm' like classical mechanics is to quantum mechanics, and quantum mechanics is to QFT.
Also by definition it only applies to inertial frames, which don't strictly speaking actually exist - even in intergalactic space. Its very hard for a law to fail in a drastic way for a conceptualisation. If it did fail you simply say that conceptualisation is not applicable here. I would say its of course not impossible, but it would be a pretty unusual thing.
To be clearer the modern definition of an inertial frame is one such that all points are the same, all directions the same, and all instances of time the same - as far as the laws of nature are concerned. Its easy to see all such frames must move wrt each other at constant velocity. All the POR does is adopt the maximum symmetry in such a situation - that not only are the laws of nature the same in each frame - but between frames as well. If, say for example, we find a constant of nature changes with time then that would not violate the POR because we can simply say that it has that value is not a law of nature. That's why the thing is so hard to invalidate - we actually decide on what a law of nature is.
That said - difficult to invalidate does not mean impossible eg if an actual aether was found that would not mean the laws of nature are the same in all inertial frames - it would depend on the direction of the aether wind in your frame.
Most that adhere to an aether are cranks that do not understand the physical implications - but a few aren't and its interesting to see their views eg:
http://ilja-schmelzer.de/glet/
Thanks
Bill