The problem was traced to the behaviour of the ports on Cisco switches. The STP (Spanning tree protocol) does not unblock the port prior to the PXE agent's attemp to get an IP therefore PXE requests are not transfered during port discovery.
Two solutions to the problem are:
PortFast needs to be configured on the switch to open the port on the network sooner so that the PXE client can get an IP.
Configure the switch so that a port is already configured for a directly connected host so discovery time is reduced allowing pxe broadcasts to the port.