Thanks for the suggestion. I've looked into Mono+Linux as a solution but I (unfortunately) need the server to host an Umbraco CMS instance which apparently doesn't work well with Mono.
There is also Amazon, http://aws.amazon.com/windows/.
I found this on the internet, http://kevinfitzgerald.net/articles/umbraco-and-mono.htm and I am sure you have seen it too. Mono's beta 3.0 release looks promising, once it hits stable there is a good chance Umbraco will be less painful to use.