He saw it coming - Er hat es kommen sehen. I understand it's not 'gesehen' because sehen is treated like a modal verb. However, if I were to say "he must have seen it coming" by adding 'er muss', it becomes "Er muss es kommen gesehen haben", instead of just kommen sehen haben. Why does the 'sehen' gain a 'ge-' in this case?
With "sehen", the Ersatzinfinitiv is optional. Your first sentence could simply look like
Er hat es kommen gesehen.
Which would be just about as correct and idiomatic as your example. "sehen" doesn't necessarily have to be considered a modal verb here.
Your second example, without the "kommen" looks like
Er muss es gesehen haben
(Remember Ersatzinfinitiv is optional with sehen)
er muss es kommen sehen haben
is just as correct and idiomatic as your example
er muss es kommen gesehen haben
lots of infinitives in a row, however is a complex thing that most native speakers' "Sprachgefühl" wants to avoid, so it remembers "ah, this was optional" and evades it.
Let's use an example where the Ersatzinfinitiv is not optional (because we're using a "true" modal verb). Assume you want to say
We will have had to accept our fate [Futur II]
this translates to
wir werden unser Schicksal haben hinnehmen müssen
No way to avoid the four infinitives in one sentence here.