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.