Thanks for the quick responses!
Before I follow the tutorial George gave me, I will provide you with a few more details. The devices are called UP Boards: http://www.up-board.org/up/specifications/
These are 64 bit Intel Atom devices which support UEFI. Their BIOS is American Megatrends Aptio Version 2.17. Before I do the PXE process, I flash the BIOS of all devices to ensure they are all running the same version. Unfortunately, they only have a HDMI port for display.
I am not ruling out a problem with my BIOS firmware provider; I believe it could be a problem with some sort of check for PXE booting where it checks for Ethernet media and some sort of display.
Just to be crystal clear on the situation: all these devices are exactly the same hardware wise and they all have the same firmware. They are all able to PXE boot but only if HDMI is connected.
I will get back to you guys with tcpdump/wireshark.