That's a very good question, and one that I haven't seen answered in a satisfactory way. People rarely think about this particular issue, much less try to solve

That's a very good question, and one that I haven't seen answered in a satisfactory way. People rarely think about this particular issue, much less try to solve it. It's one of the reasons I consider SSH unsuitable for unattended batch communication between servers. What I would try is running just after installing a machine a registration script that reports server's public SSH keys. Then it would be quite easy to generate a system-wide known_hosts file on a server that would be used as a jump host (sometimes it's called "bastion host"), or distribute it in any other way. Note that Puppet with its most popular deployment method, with master node, uses registration process and reports SSH keys (and other information) back to the master.