"Host key verification failed": what it means and how to fix it safely

You try to SSH into a server you've used a hundred times, and instead of a prompt you get: Host key verification failed. Before you reach for the nuclear option (-o StrictHostKeyChecking=no), it's wo