Effective way to ensure "clean slate system" for continuous integration service

Solution 1:

Take a look at Chef / Vagrant. Not sure if it will be fast enough, but something to look into.

Just in case you aren't familiar with Chef, it is a server designed to allow simple code based provisioning of servers. I'd recommend taking a look at one of the webcasts. Django Chef Webcast

Vagrant, veewee, chef-solo & knife-solo stuff I think this one covers most of what you want to do.

Vagrant Blog post A blog post showing a quick setup of a server using Vagrant.

Solution 2:

Have a look at Jenkins. It has plugins that allow you to run builds in virtual machines in VMWare or VirtualBox or in the Amazon/a Eucalyptus cloud. For virtual machines run in the cloud, you can specify an init script where you could take steps like installing packages.