Another mechanism to limit the exposure by short hashes is
that the first time a host performs the PK challenge with the peer
it records the actual public key.
Yes, this is a very good way to handle this. This is what SSH does.
But why stop there if you can simply download *all* site keys and store
them locally beforehand if you're sufficiently paranoid?