Is it possible to create new hosts automatically from knownhosts?

Here's my situation: I'm setting up a test harness that will, from a central client, launch a number of virtual machine instances and then execute commands on them via ssh . The virtual machines will have previously unused hostnames and IP addresses, so they won't be in the ~/.ssh/known_hosts file on the central client.

The problem I'm having is that the first ssh command run against a new virtual instance always comes up with an interactive prompt.

The authenticity of host '[hostname] ([IP address])' can't be established.
RSA key fingerprint is [key fingerprint].
Are you sure you want to continue connecting (yes/no)?

Tell me the best way to get the host to know its host? I'd really like to avoid having to use expect or whatever to answer the interactive prompt if i can.

The best way to do it is the following

ssh-keygen -R [hostname]
ssh-keygen -R [ip_address]
ssh-keygen -R [hostname],[ip_address]
ssh-keyscan -H [hostname],[ip_address] >> ~/.ssh/known_hosts
ssh-keyscan -H [ip_address] >> ~/.ssh/known_hosts
ssh-keyscan -H [hostname] >> ~/.ssh/known_hosts

That will make sure there are no duplicate entries, that you are covered for both the hostname and ip address, and will also hash the output, an extra security measure.