The dreaded ssh "Roaming not allowed by server" problem

Passwordless login via ssh is a great technique. It allows you to turn off user challenge authentication altogether, and so shut out those robotic hackers who try to guess your user name and then try every password until they break in. With passwordless login they have to forge a long cryptographic RSA key which, given the number of possibilities and the latency on the line, is impossible. So when I went about restoring a server that had been hacked I put back my old ssh key, and tried to login. No joy. ssh -v mysite.com produced a mysterious ssh error: "Roaming not allowed by server". What does this mean, and how do you fix it? Googling the answer didn't help. No one seemed to know the answer. They were all fixated with file permissions, which may be an issue, but does it cause this error? Without reading through the open-ssh code here's what I found: delete .ssh/known_hosts on the client connecting to the server and all will be well. If the server's domain-name is dynamic, or has been altered (as in my case) then that counts as "roaming". When your IP address changes ssh will complain that a key in known_hosts has offended it. But when the server's address changes it will give you this "Roaming not allowed by server" message.