I've got a Windows 2008R2 standard server running DHCP services. We've noticed that certain clients are receiving inconsistent DHCP replies. We have over 175 Windows workstations in this VLAN that don't seem to have trouble getting DHCP leases. However, PXE-booting clients trying to reach our DHCP server are able to get a lease inconsistently. Additionally, we tried using the "dhcping" tool against our DHCP server and found that roughly two of every three requests time out with "no answer" -- and this holds true when we set the timeout value on dhcping to 20seconds. After a failed attempt, however, we may get a dhcp lease reply immediately with dhcping. This leads me to believe that this issue isn't confined to PXE booting clients, but something more systemic with my LAN layer2 or DHCP. And that possibly my 175 windows clients are experiencing this in some form without my knowledge. We have over 30% of our scope available so the addresses are there. I was unable to find anything in the Windows server "DHCP-Server" log. Of course, my goal is to have my DHCP server reply to every request that it receives on the LAN!
As you mentioned you were using VLANs, I am assuming your PXE vlan & Windows vlan are separate... and/or you have 1 DHCP server serving the various VLANs with their appropriate address. Have you looked into the appliance/software package performing the Relaying? (DHCP doesn't traverse routes without a relay. Some appliances call these a "helper" service) Perhaps your helper service isn't configured properly or is having troubles keeping up.
My suggestion would be to run a packet capture on the DHCP server and look for DHCP packets coming in to the DHCP server, starting with the DHCP Discover packets. Try to key on one client so that you can identify the packets that are captured. If you don't see DHCP discover packets reaching the server from the MAC address of the client you're keying on, then the packets are likely getting lost in the network. If they come in but don't go out, then it's a server/service problem. If they come in and go out but don't make it to the client then it's a network or client problem.