We've run into this exact problem, but in a very serious way -- our new startup extends Amazon EC2 into a Virtual Lab environment (multi-user, policies, sharing etc.) and so we needed to speed up the start time of Windows machines. Our biggest decision was to support only EBS based volumes in our application, because they're the only ones that can start up in 5-10 minutes. In our testing we found instance-store startup times to vary widely and sometimes take excessive amounts of time, which made them useless for us.
Simon @ http://LabSlice.comLabSlice Virtual Lab Management on EC2