Alternately, you do have that problem with SSH, and you work around it by scratching your head, saying "oh, right, because I switched hosts/reinstalled the OS/ran that mysterious command," and then nuking the key entry.
Alas, this does not scale well into the HTTP realm.
What about trusting not the key itself, but the CA which signed the cert - whose cert came within the cert chain upplied by the server ? Then everyone could get their own "root" CA and renew the certificates to their heart's content.
Alas, this does not scale well into the HTTP realm.