In all of these cases the DHCP server is handled by the customer's IT "department", I will have to talk to them and see if we can switch it to 125. I don't think this is a DHCP issue though, it is being handled by Windows servers in all cases, and if jump into config mode of the phone when it is like this everything in the current IP settings is correct, it just can't seem to make the MiNet connection.
EDIT: Scratch the possibility of it being a DHCP issue, my on-call tech got a call of this issue last night at a car dealership (one of the ones having this issue), and as I quizzed him on it some this morning he reminded me that this site doesn't have DHCP at all, the entire network is all statically assigned. When he was troubleshooting this he tried plugging the phone into several open spots on the Edgewater switch and it did the same thing, went to the back where the phone system is with a little 5-port switch connected and a POE injector ahead of the Edgewater switch and the phone booted fine, reset the switch and then worked again. Looks like the next time this happens it is grab some captures and go back to Edgewater Networks and see what they say.