The Amazon windows instances reboot on start because the default configuration of the "EC2 Config" windows service is to rename your host to the internal DNS name of the instance. Renaming hosts requires a reboot on windows. If you do not need to use the internal DNS name of your instance then you might benefit by disabling the SetComputerName feature. Windows instances also have the advantage of not having to initialize the startup drives where you might have already bundled your configuration again saving some more time in instance start up. All of this is possible via the EC2 Windows Configuration Service.
Windows Configuration Service:
My Windows small instances normally take 15-18 minutes to boot (larger ones are faster). Depending on your requirements, you might be able to bundle all your software within the AMI and be able to have everything boot up and running within that period. I understand the reservations for not bundling everything into an AMI but it might be worth the improvement in start up time to have production AMIs with everything bundled in them. Keep the build scripts separate if you want in your build environments.
Additionally, now that Amazon had released EBS root volumes as opposed to instance-store root volumes. Windows small images running on an EBS volume boots up in almost 5 minutes versus the almost 20 minutes it took before. Also you don't need to terminate - you can stop/start them - depending on your setup this potentially shaves a few more minutes in some start up scripts.
Essentially customizing your Windows EC2 Config service, your AMI and potentially using an EBS boot volume should reduce start up times to almost 5 minutes. You can avoid the sysprep that run on an ec2 instance startup depending on your app, especially for development purposes. An non-sysprepped m1.large image that avoids a hostname change on startup can start up in about 2 minutes which is not bad at all.
At this time, as far as I understand it, that's the best you can do with Windows on Amazon EC2 but that really is not too bad. If you are able to forecast close to 10 minutes in to the future based on average usage patterns, you should be able to spin up extra instances and handle the additional load.