Check out U of T's Snowflock. Very fast VM cloning and destruction.
Ach, I see now what eru meant by copy-on-write VMs.
(At least as long as you have a general purpose operating system. A special paravirtualised would probably not need to make much of a difference between booting and resuming. But that's only a theoretical musing for your circumstances.)
This is my new plan of last resort if I can't prevent the current sandbox from failing.