In case anyone else has the same problem, here is the issue.
The APIPA registry change had a side effect of speeding up the DHCP process, and this unmasked an incompatibility between DHCP and the Spanning Tree Protocol on our switches. STP blocks traffic from newly connected devices for 15 seconds, and now our DHCP process was completing in the 15 second period - so no requests were ever reaching the server.
The solution is to configure all your switches to use STP Fast Mode, assuming you want STP. For very small networks with a single switch you could just disable STP.
I expect others will have this same problem.