If someone were to upgrade/change their server OS or generate a new
key for purely non-malicious reasons, this could happen, no?
that's true. But if you disconnect, reconnect, and get the old key, something is funky.
fwiw, that's what's happened to me. And I know the ssh key on the server hasn't changed.