Is it possible to make the ssh client not care what IP a ssh server is behind (and if a different server was behind that IP earlier) but instead trust specific server keys? (And maybe nickname those keys?) I use dynamic DNS and I have IPv6 privacy extensions enabled on some computers and am always getting asked if it think it's safe to connect. Another possibility is addresses assigned by DHCP getting assigned to different ssh servers and causing all sorts of 'key doesn't match IP' errors.
Add a nickname for your server in
~/.ssh/config, and turn off
CheckHostIP for this server.
Host nickname HostName example.dyndns.org CheckHostIP no
Before you connect to the server for the first time, you can copy the public key out-of-band: grab
/etc/ssh/ssh_host_rsa_key.pub from the server, remove the
root@hostname part at the end of the line, add
example.dyndns.org at the beginning, and append the line to
~/.ssh/known_hosts. Optionally run
ssh-keygen -H to hash the host name (this is only useful if you're concerned about the privacy of that entry if someone steals your hard disk or your backups, which for 99.99% of people is useless because the information is present in some other nearby location anyway).