Unless “the machine is taken over” means firmware-level compromise (e.g. disk controller, NIC controller, …), in which case the next customer allocated to that machine can be compromised despite full disk erase between customers.
I'll agree with this attack vector, although it'd be trivial to have your PXE boot routine between customers re-apply known good firmware to the NIC and disk controller and verify with checksums (unless there's a 0-day out there for the NIC controller, in which case you're owned regardless).
Normally the PXE boot code is, itself, stored in firmware.
Whatever components start first, wins. If the PXE boot code is in the NIC, you can theoretically verify the rest of the system first. If its in the BIOS, the BIOS needs to trust the NIC as untrusted/determine if its compromised or not.
Security is hard :/
ROM based NIC? Why not? If you're going into large scale dedicated servers, this is not exactly impractical. You could probably also just disconnect the flash enable pins on the ICs.
Assuming the firmware has no say in the flashing process.