Isn't the whole point of VisualHostKey in ssh to act as a security mechanism, i.e. "yes this looks like the correct server key" on first use on a new client that doesn't already have the key in known_hosts?