Technology for short-lived private VMs

Solution 1:

Some ideas:

1. Your point "hundreds of VMs on reasonable hardware" makes me (without personal experience) think of VMs that either boot over the network or share most of their volume space (/usr) via NFS. Depends on how similar your VMs are.
2. "What little I could get working was fragile as hell" Hard to believe. Can you be more precise what the problem is?
3. "would be difficult to install onto a real machine" You mean "difficult" compared to what, to the wanted 1-click solution for VM creation? I would ask: How difficult is this and how often is this going to happen? What is the difference, recreating the initrd for the respective hardware?
4. "however I can't post-install it enough" What you you wand/need and why does that not work? You could make the download of a script part of the boot process. The VM gets its IP by DHCP (hard configured to the VMs MAC address) and Samba delivers different post-install scripts to the VMs, depending on the IP address of the client.

Solution 2:

While reading your post I kept thinking that vagrant and jenkins with the vagrant plugin would fit your needs pretty well. Any box you have that can actually handle the number of VMs you're talking about shouldn't even notice the overhead of the tools maintaining the environment.