> One solution could be to keep machine images stored, like AMIs, and use a tool like Chef or Puppet to re-deploy a known good configuration.

It's probably Norton Ghost, and I'd put $5 on the Ghost image being cooked bad.