When connecting to a server in the same DNS domain using an unqualified hostname, it can be problematic to find a safe pattern to allow an @cert-authority record to validate a host certificate. It would make host certificates much more useful if either the hostname of the server were canonicalized before matching against the @cert-authority record, or (as suggested by Damien) the ability to match against the IP address using CIDR notation were added.
The change to support %h expansion in ssh_config Hostname options has been checked in and will be in openssh-5.6. This should allow the hacky approach that we discussed on the mailing list: Host *.* Hostname %h Host * Hostname %h.my.domain.org Without requiring new API from the resolver, I can't think of a better way unfortunately.
With the release of OpenSSH 5.6p1 this bug is now considered closed. If you have further problems please reopen or file a new bug as appropriate.