> There would be no DNS configuration at all, all local machines would use anycast DNS for the services and a well known server for Internet addresses.
The solution there is DDNS, which is one of the things behind MS AD and just works, and configuring that on pure Unix infrastructure is surprisingly easy.
Assumptions and dragons be here.