This is actually a bad user experience problem: To generally omit the manual verification of SSH key fingerprints I am using SSHFP. With fully qualified domain names (FQDN) as the hostname for SSH connections such as ssh nb10.weberlab.de this works perfectly. However, admins are lazy and only use the hostname without the domain suffix to connect to their servers since the domain search does the rest: ssh nb10. Not so for SSHFP which fails since the default OpenSSH client does not use canonicalization for its DNS queries. Hence you must explicitly enable canonicalization for OpenSSH.
