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.).