If I recall correctly, the S50 is quite an old model, so may be worth checking that you have the latest bios.
If this is one of the beasties with Hyperthreading - try turning it off in the bios as well.
I cannot recall whether there were any PXE or NIC specific bios settings - I'm thinking as to whether the NIC is initialising with the correct speed for your LAN switch.

Thanks Edt,

disabled Hyperthreading =NO GO

have folowing NIC settings in BIOS
PXE Boot Agent = Enabled
PXE Base Code = Enabled

will double check on BIOS update after lunch:-)

Assuming there are no bios settings which control PXE booting, and the boot order in both working and failing machines is consistent, then I would conclude that your investigation is pretty much spot on.
Do you have a Lenovo tech support contact, or failing that, have you had a look in the Lenovo forums to see if this issue has been raised before?

Having same issue with HP dx2400 desktops with a realtek nic onboard. It really is strange because every once in a while these desktops will boot. All desktops are up to date with bios updates. On the other hand our HP laptops are PXE booting just fine. Have went as far as rebuilding the whole enviroment and moving the DHCP responsibility to another device. Would love to hear a soulution. Ghost server = win 2003 GSS 2.5  current with all updates as of today.

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.

soon as PCI NIC used then same issue.
Will now look at the network hardware especially speed settings (AUTO, 10/100/1000)
Im also pretty sure the issue is actually on the conf of Switch/Router used

Cant update as quick as I would like to since no high prio on this right now

I had this same issue with DX2400's and just re created my PXE boot disc in PXE utility. I selected the Altiris Realtec NIC driver 8111c family and it worked fine. Imaging these with MS dos though and not WinPE.