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.
Haven't yet encountered it in the wild though