Or they automatically distribute the host key fingerprints onto employees machines via some organization-wide internal method (ldap, orchestration/configuration management tool of the month, ssh_config pointing to a global known_hosts on a share, etc.).

OpenSSH also supports certificates, so you can have the host system provide a certificate identifying it -- but you have to setup a CA, and arrange for new hosts to securely have their host keys signed by it.

"Ideally they set up SSHFP dns records with the hostkey fingerprints ..."

We (rsync.net) are doing this in 2019. A little embarrassed we haven't done it already ...