> Where could you rent VMs in 2006?

I was renting a Debian VM from Bytemark in 2005 that I used to host a mail and web server. I think they were one of the first operators in the UK.