I'm not so convinced it is that complex on a homogeneous OpenBSD network. OpenBSD is a very manageable system, such as the entire OS contained in compressed tarballs for easy extraction and the flexible ports system. Both of these entities are easily scriptable. Then all there is to worry about is system configs and custom binaries, which can be easily managed by CVS. A hierarchal CVS structure can be built to mange global (all nodes in network), group (groups of similar servers), and single (things specific to a node, like /etc/myname) nodes. You apply global settings first, overwriting with more specific settings.
For what it's worth, in our various environments (eg. testing, production, development, etc., each with up to 45 or so servers running mostly RedHat Advanced Server) as well as for other internal services we've found CVS and a script to push modifications to affected servers to perform fairly well. That said, to my knowledge no one here has spent much time looking at cfengine or other alternatives, but a move to such a system would probably be viewed with (guarded) enthusiasm. -Josh