Thanks Nihil...
I doubt if anyone here (apart from yourself) handles anything like that number of servers.
Wow so the way you responded there almost makes it sound like I came off as a bit of a braggart. That was by no means my intention in mentioning the size of our environment, I only wanted to make sure everyone had an understanding of the problems we were running into.

You guys have encountered scalability problems so I guess we would not feel confident in suggesting solutions that we only know to work in much smaller environments.
Yeah I guess that makes, I wouldn't feel confident in making a suggestion like that either.

Have you considered a tiered or devolved deployment strategy? such as making each data centre responsible for locally applying policies devolved from the mothership?
Yep this was the direction I was heading for creating an in-house solution, unfortunately we let one of our datacenters get a bit too large. Even to the point where our IPMI cards no longer work due to arp-cache being full So we might have "mother ships","father ships", and maybe even some little "child ships". I've also heard stories of people forcing puppet to behave in a similar fashion with crons and just remove puppet-master altogether.

You might try to make contact with IT people at NASA, government departments, and the military, and ask them what they use/suggest.

Otherwise Google is your friend.............I believe they have the most servers of anyone in the commercial sector...........you need to talk to your oppo at Google?
Great, I wonder if NASA or the US government has an employee directory for all their IT grunts I can just start war dialing . Seriously though, if anyone on the list has any contact for someone like Nihil is suggesting, please shoot them my way(or ask them and then post back here on the thread). I would be greatly appreciate it.

I also would be interesting in anyone's thoughts or ideas for architecting such a scalable configuration management system. So if anyone's specialty is in designing scalable software please share.