I was big into Bitcoin about four years ago and work for an ISP nowadays. We provide services as well and I've considered mail/web hosting/VPS/dedicated offerings (on a small scale) with Bitcoin as a payment option but I don't want to end up attracting the "wrong type" of people.
I realize that there are people who simply want to be anonymous and I'm totally fine with that (I do run Tor relays, for example) but my fear is that the majority of customers this would attract would be those that are "up to no good".
Thinking out loud, perhaps a mail hosting service payable with Bitcoin would be a good way to test the waters -- that is, we could take care of domain registration, DNS configuration/hosting, etc. and allow access over Tor for those looking for "anonymous e-mail" (although I'd be implementing pretty low limits on volume, at least initially).