User crissi provided files needed to reproduce the problem. That was very helpful. Confirmed the hang here with PXE over NAT.
The actual problem is completely unrelated to networking. It's greatly contributed to gPXE's creative use of big real mode, A20 control, and similar horrors.
From what I can tell, gPXE sets up big real mode which doesn't work quite right in VirtualBox only on Intel CPUs with old VT-x implementations with no unrestricted execution support (when VT-x is used). I haven't tried but doubt that AMD-V is affected.
I changed the ticket to reflect the situation. The guest type is in fact not Linux here, it's gPXE doing awful things to the poor little CPU.
