It would be interesting to test whether adding in another NIC card with PXE boot capabilities into these desktops would make a differerence - perhaps in line with disabling the on-board NIC as well.
If the problem persists, then I would be looking more closely at the networking hardware, switches, etc, in case there is a problem with the correct link speed being selected automatically.
If the problem disappears, then I'd be pressing Lenovo or HP to sort out their hardware.
Again, don't overlook the possibilities of the user forums - Lenovo certainly have them, and I'd hope HP would also. These forums are excellent for gathering information on whether others are seeing the same problems with this specific hardware.