Surely the problem is lack of inexplicable data? e.g. relativity had constant speed of light in all directions.

Sure, we could come up with theories without suc data, but the search space is just too inconceivably big to explore. We need constraints to narrow it down... and to have a reason to think it might be true.

Empirical precedes theoretical.