There could be a solution in-between the 2 options I proposed in the description:

Asking administrators to generate keys affected by the unordered default type attributes is not a realistic solution, however enforcing the key/salt types order removes the possibility for service administrators to configure custom prioritization for their services if they wish so. As an example some admins may want to prioritize Camellia over AES-SHA1 for their service.

So I think an optimal approach would be to enforce a certain order of default key/salt types, on both the configuration list (to make sure newly created keys are ordered the right way) AND the principal keys (to prioritize the strongest types, even if the key list was encoded in the wrong order). This ordering should be done based on an LDAP attribute (we could call it krbOrdDefaultEncSaltTypes), rather than an hard-coded list to simplify the update process, and enable its modification without requiring an IPA update, to deal with a security vulnerability by example. This new attribute would be a single-valued string attribute used as a space-separated list of encryption/salt types ordered by descending preference.

Such an approach would make the krbDefaultEncSaltTypes attribute useless. What we could do we it is use it as an indicator of whether key list reordering should apply or not:

• krbOrdDefaultEncSaltTypes doesn't exist and krbDefaultEncSaltTypes exists = Use key/salt types config from krbDefaultEncSaltTypes (probably invalid) and key list as it was stored
• krbOrdDefaultEncSaltTypes exists and krbDefaultEncSaltTypes exists = Enforce the value and order of krbOrdDefaultEncSaltTypes everywhere (configuration and order of keys)
• krbOrdDefaultEncSaltTypes exists and krbDefaultEncSaltTypes doesn't exist = Use key/salt types config from krbOrdDefaultEncSaltTypes (proper order) and key list as it was stored

This way, an domain admin wishing to re-allow service admins to use their own key types order of preference could do so by removing the krbDefaultEncSaltTypes attributes. This behavior would also apply to new domains, as they won't be initialized with krbDefaultEncSaltTypes (only krbOrdDefaultEncSaltTypes would be set).

A question remaining is: what to do with the krbSupportedEncSaltTypes attributes? They are only supposed to be about filtering the requested list of key/salt types when generating principal keys. This should not require any ordering. However, in the code we can find operations like this one, where the list of key/salt types provided by password change request are compared to the configured list of supported types, and if there is an exact match (i.e. same order), the request list is replaced by the default types list:
https://github.com/freeipa/freeipa/blob/release-4-12-4/daemons/ipa-kdb/ipa_kdb_passwords.c#L188-L202

So it seems the order of the supported key/salt types has an impact on the behavior of the KDC too.

I wonder if we should derive the krbOrdDefaultEncSaltType or reorder krbSupportedEncSaltTypes according to the permitted_enctypes in the Kerberos configuration on the KDC side? This way we would follow crypto-policies and don't need to explicitly define the order. Admins will have an easy way to affect the order by setting krb5.conf parameters (or changing the crypto policy) and restarting the service.

Inferring the order of krbDefaultEncSaltType based on permitted_enctypes from the krb5 host configuration could work. The problem is: how do we deal, as an example, with the situation in a gradual upgrade environment were an IPA version has both AES-SHA1 and AES-SHA2 as default types, and where an IPA replica with a newer version has AES-SHA2 only? Sticking to this rule would mean having a different set of key types generated depending where the ipa passwd or ipa-getkeytab request lands.

About keys reordering on access, on the other hand, the question is how to deal with the key types that are no longer matching permitted_enctypes (because they were generated on a version was not yet in place, or where the type was still permitted)? Should we simply put the permitted type keys in front of the list, and leave the others at the tail of the list?

On this regard, we also have to decide how to handle the special case of RC4-HMAC, which can be allowed, even if the type is not part of the supported ones:
https://github.com/freeipa/freeipa/blob/release-4-12-4/daemons/ipa-slapi-plugins/ipa-pwd-extop/ipa_pwd_extop.c#L121-L126
https://github.com/freeipa/freeipa/blob/release-4-12-4/daemons/ipa-slapi-plugins/ipa-pwd-extop/ipa_pwd_extop.c#L179-L184
https://github.com/freeipa/freeipa/blob/release-4-12-4/daemons/ipa-slapi-plugins/ipa-pwd-extop/ipa_pwd_extop.c#L1320-L1324
https://github.com/freeipa/freeipa/blob/release-4-12-4/daemons/ipa-slapi-plugins/ipa-pwd-extop/ipa_pwd_extop.c#L1728-L1732

Here is the commit message I wrote for the pull request I am preparing. It summarizes the changes and the reasons why they are needed:

Standalone MIT KDC instances are using the "supported_enctypes" kdc.conf
parameter to determine which key types are accepted when setting a
principal's credentials. The order in which keys are saved in the KDB is
the same as the types provided by the admin. If the admin did not
provide an explicit list of key types, then the full list of
"supported_enctypes" will be used (still preserving the ordering).
The ordering of principal keys is important because it determines which
encryption type will be use the generate the ticket to this principal.
When the KDC processes a ticket request, the session key type is
selected based on the list provided by the client (depending on its
"permitted_enctypes", "default_tgs_enctypes", or "default_tkt_enctypes"
krb5 configuration parameter), and the KDC's "permitted_enctypes". But
the ticket encryption type itself will be the one from the first
principal key allowed by the KDC's "permitted_enctypes". Here
"permitted_enctypes" only acts as a filter, it has no impact on
encryption type priority.
As a consequence, the explicit list of key types provided by the admin
or the list of default key types (i.e. "supported_entypes") at the time
the principal credentials are set, will impact the encryption type used
for generating the ticket to this principal until the credentials are
modified again.
IPA separates the notion of default and supported key types. So far,
they were configured as the LDAP attributes "krbDefaultEncSaltTypes" and
"krbSupportedEncSaltTypes" respectively. However some design mistakes in
the way these attributes where stored and updated may cause key types to
be read out-of-order (i.e. not the strongest type first and the weakest
last). But as explained earlier, fixing these attributes alone will not
fix the keys that were generated in the meantime, and might already be
stored out-of-order.
Hence this commit introduces 2 changes to fix this problem:
* The "krbDefaultEncSaltTypes" and "krbSupportedEncSaltTypes" LDAP
  attributes are now ignored. Instead, the default key types, supported
  key types, and initial master key type are inferred from the IPA
  server's "permitted_enctypes" in the krb5 configuration. This will
  ensure there is no mismatch between the local and domain-level
  configurations. It will also make IPA more portable because it removes
  hard-coded encryption types settings, to function according to its
  runtime environment instead.
* When a credential update request features an explicit key types list,
  it will systematically be reordered and filtered according to the
  server's "permitted_enctypes" setting. And so it is for existing list
  of keys in principal entries.
To be mentioned that putting this change in place required to modify the
output format of "ipa-getkeytab --permitted-enctypes", which is now
using the same format of encryption type names used in krb5
configuration files. This command is now used as part of a domain's
initial setup.