“But typically how do we handle the very possible use case of each package deployed in the IS having their own External ID as required?”
I must disagree with the notion that each package deployed might have their own external ID. The needed number of external IDs is typically fewer than 5 and is quite often just one or two (DUNS and Mutually Defined are the most common). It is also common to have one or two IDs from applications that identify partners–how many such applications do you have?
For TN there is only one external ID required. Never more than one. You can add all the custom external ID types you like, XYZ, ABC, and DEF and TN will still only ever require the one external ID. It is not possible, AFAIK, to configure TN to require more than one external ID for its profiles.
Each of your packages needs to understand what to set for the external ID type it wants and what to set for the TN required external ID.
“For instance there are three required External IDs that are defined as required, say XYZ, ABC and DEF. Each External ID has been added as required by different packages. So there is very much possibility that not all profiles that are to be created would be able to define all the three External IDs.”
Which would indicate those external IDs cannot be required, they must be optional. But as I mentioned, there is no way in TN to make all three of them required anyway, so the point is moot.
To sum up, you must set the required external ID for all profiles before the profile can be made active. There is only one required external ID. You cannot require more.