Although it's not what we use, here's a program that does a similar type of management: http://warewulf.lbl.gov/trac If you take the time to combine Warewulf with something like Puppet or Chef, you'll have a nice system for managing 100s of thousands of machines (I could easily see this scaling to over a million servers if you have the cash to build something like that).
If you're wondering about dynamic libraries in an environment like this, take a look at https://github.com/hpc/Spindle
And yes, I still get giddy when I type one command to reboot 10,000 servers.
ISC DHCPD is pretty bulletproof. Many large carriers/ISPs use it, so scaling this end should be pretty straightforward. You'd probably want to statically configure leases for all your servers though.
Pretty much all PXE roms built into NICs only support TFTP. I would use TFTP to load a iPXE, then use iPXE to load the operating system over something else (probably HTTP). Scaling HTTP is well understood (this is about the easiest HTTP scaling you can do, downloading a few static files).
Nothing about this is hard to scale, nor does it require any special network setup.
My standard install is to embed a script into iPXE that chainloads a config file over TFTP (this works properly with non-ISC DHCPD servers, like OpenBSD's fork and dnsmasq), then loads various OS's and diagnostic tools over HTTP or NFS.
So much easier than slinging around optical media or hard disks for installation/diagnostic/booting diskless clients.
Using PXE in your environment means you have to feck around with DNSmasq, or manually configure DNS, or use enterprise-level bloatware.
The suggestions above to use iPXE and switch to TCP transfer methods such as HTTP make a lot of sense in that aspect.
Like pretty much anything else, it's not a problem when implemented correctly.
Even if you have hundreds or thousands of machines, it's not that difficult to configure your network switches (assuming you don't buy your network gear at Office Depot) to distribute the DHCP and TFTP across multiple servers -- if you even need to, that is; DHCP and TFTP are two of the most lightweight networking protocols in use.
http://www.rocksclusters.org/rocks-doc/papers/two-pager/pape...
Rocks is used at production cluster installations with thousands of servers.
http://www.rocksclusters.org/rocks-register/index.php?sortby...
Also most likely makes it harder to reuse most of the trusted boot infrastructure that already exists for Linux. So we can assume at least in the initial release Mallory can race with the real PXE server assuming a network that hasn't been partitioned with a crazy complex config (i.e. basically all of them).