A second specific comment
The configuration of a system is much more complex than most configuration management tools consider. The tools generally limit themselves to the list of things a "sane" person would change.
The list of things that actually affect the running of your system is much, much larger.
- Libraries. Did you hand-jam in a specific openssl version for some application?
- Programs. Did you hand-upgrade openssh on one system?
- /usr/local. Is it in the path of a shell script used to launch a service? Is everything under it managed?
- Permissions. Did someone do "chmod -r" somewhere they should not have?
If you write rules in puppet to handle all of that, your set of rules blows up to be insanely detailed, long, and completely unmanagable.
But the reinstall handles it all. In an automated, scripted fashion that allows you to easily change what you need.
Seriously people. Cobbler & similar install servers. They need to be part of any large scale host management. And since they are already there, are easy to leverage into being a large part of your large scale host management. And then reinstalling the server is the sane solution.