Canonical's Landscape makes it very easy to manage many machines at once.
You could just have a centralised key store and, on demand, push out changes to every machine's known_hosts file.
Alternatively, if you don't want to use Landscape, how about simply synchronising the known_hosts via rsync? I'm not all that familiar with all this enterprisy business, but it should work very well.
Assuming the company's computers get shut down every night, i would do this:
- Have on some server a centralised known_hosts file that you manage manually.
- write a very simple program that, at boot time, tries to fetch that file and replace the current one
- on the administrative side, test all changed to the master-file before pushing it out, which you do by just replacing the one all the clients try to access.
you could use RCS, an old sysadmin's favourite, to manage different versions of your master-file.
Note that many sysadmins will tell you that centralising things is a security risk, and generally not a great idea.
Now, I'm not a sysadmin (and therefore not to be trusted on this matter). You really should ask this question on serverfault
LDAP seems to come up there quite a lot. Here's a bit information about fetching SSH Public Keys from LDAP, and here's some more.
This question might also be of interest to you.
I hope this is helpful. As you've discovered yourself, managing ssh access in large setups really is quite complicated.