If you had a perfectly clean install of your distro of choice, could you write a shell script that could build your server from scratch?
If you can answer Yes to that (and you should), then you can build an if/then-heavy shell script that works with each of the APIs to create a perfectly clean install of your favorite distro.
One script to create the clean slate machine.
One script to build what you need.
We have 9 "pods" around the globe, each with API servers (Java/Tomcat/Apache), static servers (Varnish), a MySQL slave, and an HAProxy Maître D'. With close to 60 servers, our monthly bills are less than $1,000, and we haven't had downtime in years. Spinning up a new server is just: sh build.sh atl api 1.
Feel free to ping me if you want any more details: mark@areyouwatchingthis.com.