Just though I'd let those who are interested know that FeralHosting are now accepting Bitcoin payments again.

I used this company about 2 years ago and they are quite something.