Before you choose a hosting provider, always check their reputation with Spamhaus.
I rent virtual servers with Bluemile (formerly also Fivebean). This morning I was greeted with bouncing E-mail, and a quick check showed:
Ref: SBL99441 184.108.40.206/20 is listed on the Spamhaus Block List (SBL) 30-Nov-2010 08:26 GMT | SR02
BLUEMILENETWORKS.COM ignores spam complaints, hosts spammers including known spam operations (ROKSO), assigns non-SBL'd IPs to spammers who get their assigned IPs listed in SBL, provides snowshoe spam configurations, fails to provide rwhois information as required by ARIN (thus providing anonymity for spammers) and generally acts like a network unconcerned with its mailing reputation. Spamhaus thereby treats it accordingly.
Here's a link to the actual updated spamhaus page, which might be different when you look it up. Notice that's a /20 block that is being blocked — I can't do anything about it!
I reported this to Bluemile support, who were completely unconcerned. They would deal with it once an engineer comes to work in the morning (business hours). Well, several hours have passed, then several business hours have passed, and there are no results to be seen. Meanwhile, almost all my outgoing e-mail keeps bouncing, which I have zero control over.
I am not a spammer. I take extensive care to make sure my servers never relay any E-mail. And yet here I am, listed in the SBL because I didn't check my provider's reputation.
I am really angry. And for those of you who suggest changing providers: sure, but moving mail and DNS servers is not that easy. It takes time and effort.
One thing is sure: the next time I look for a hosting provider, I will check their IP ranges and check with spamhaus (and other lists, possibly) to see if they are a spammer haven. I don't want to have anything to do with providers that are.