My understanding (as explained to me by someone who did work on some CPU-like ASICs) was that they were able to produce the early versions of ICs with some form of "PROM" (possibly not the correct term) which could then be one-time programmed so that they didn't have to pay for a new set of masks if they wanted to change any of their instruction decode (or whatever they had wired into the "PROM") logic.
All they had to do was burn a new version into a blank chip and test/use it from there.
The company in question was producing low-volume, high cost products for a narrow niche and so I don't know if they had to throw away some die space to have this "PROM-like" feature and if that is still how things are done today.
I my comment earlier about EDA tools being able to "simplify" the ROM into the die was probably a paraphrasing of what I was told about a tool. The tool (or workflow) allowed a designer to go from a working prototype microcode ROM to a hardcoded gate circuit (presumably by the same sort of process that one can go through to simplify a logic statement that is in disjunctive-normal form).
This was information passed on to me second hand from quite a few years back now so I probably should've tried to look up some primary sources before writing my comment! Oh well.
What's being discussed is at the same level as microcode, whereas most of the distinctions you're making apply to the normal code storage ROMs. For instance modern microcode is nearly never a PROM.
Additionally combinatorial logic is generally made out of cheap gates, the two concepts aren't in conflict, but instead orthogonal.