On the other hand, at the company I work for, internal machine certificates/keys are renewed without my involvement (I'm a so-called "IT-owner" of some apps and the infrastructure that the apps use), and therefore I get the warning when connecting to their Linux hosts but each time (few times every few years, but still...) I dismiss it hoping that it's because of the work of the admins renewing the certificates (clarifying who-did-what-when would be a potential major administrative undertaking) => this is absolutely a flaw of the internal processes.
Yes, it could be fixed by a more complex infrastructure, but again, if the internal processes are weak then even the more-complex-infrastructure could be compromised by side-attacks.
With cross-signing, this will get even easier because cross-signed devices will be automatically trusted.