Using WDS to image a virtual machine using PXE boot fails, suspect issue is in WDS configuration

I'm trying to convert a site imaging procedure from (install old image, update image, recapture image) to (have image on VM, update, snapshot, sysprep, capture, roll back to the snapshot).

The first step of this, of course, is to put the existing image on the VM, and in order to do that, I need to PXE boot the VM. This is failing on Virtualbox on a Windows host, Virtualbox on a Mac host, and VMWare Workstation on a Windows host, but I am able to PXE boot a physical computer and image it with no issues.

The VM does get a valid IP.
I have booted the VM to a Linux LiveCD and pinged back and forth to make sure networking works.

This is the relevant section (where it fails):
WDSNBP started using DHCP Referral.
Contacting Server: 10.9.0.3 (Gateway:0.0.0.0)..
No response from Windows Deployment Services server.
Launching pxeboot.com…

On a physical computer, I don't get the "No response" line, instead booting proceeds.

Since this is failing on multiple VMs on multiple computers, I'm suspecting something is wrong with my WDS settings. Any idea what could be causing this?

Reply to comments:
Imaging a physical machine works:
(and the appearance is identical up to the no response line)

WDSNBP started using DHCP Referral.
Contacting Server: 10.9.0.3 (Gateway:0.0.0.0)..
Architecture: x64
Contacting Server: 10.9.0.3

Downloaded WDSNBP from 10.9.0.3 imaging.company.corp

Press F12 for network service boot

(When I've spun up testing VMs, I've set them as x64, so that is probably not it.)

Also, the VM and physical machine both get IPs in 10.9.0.0 / 22, so that's not the issue.

EDIT for reply to answer:
Good thinking, but that's not it. The Virtualbox extensions are installed, and it's also failing under VMWare.

Last edit:
Worked-around. Since it's a VM that's not booting, we built boot .isos that could just live on the virtual host, using these instructions: http://www.eversity.nl/blog/2012/05/windows-deployment-services-how-to-create-a-bootable-deployment-iso/