Yes. Booting up every VM would take too long. Cloning them just before you execute the payload is the way to go.
(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.)
Ach, I see now what eru meant by copy-on-write VMs.