Maintaining SSH Host Keys Across a Large Network?

skullY asks: "Like most organizations, we have a large number of servers, all of which have unique host keys. Our big problem right now is that the vast majority of our servers are in a cluster and we have one or two machines that get reinstalled every week. Every time this happens, a new SSH host key is generated, and all our existing machines bitch when they have to connect. I realize that the best approach is to install system wide ssh_known_hosts files, and keep them up to date, but in practice this isn't so easy. So my question is how does everyone else keep track of large numbers of SSH host keys that continually change, and propogate those changes to machines on the network?"