Why is shared hosting like phishing?

A client of a friend was getting rejection messages when they tried to send mail

Google tried to deliver your message, but it was rejected by the recipient domain. We recommend contacting the other email provider for further information about the cause of this error. The error that the other server returned was: 554 554 5.7.1 The IP address of web site www.client.com [75.101.163.44] is listed at www.spamhaus.org (state 18).

What? An SBL listing? The client hadn’t done anything wrong, certainly nothing that would provoke the wrath of Spamhaus. And… they’re not sending email from 75.101.163.44 anyway, they’re sending it out through Google Apps. And, wait, www.client.com is listed on the SBL – the SBL lists IP addresses, not hostnames.
What is going on here?
We’ve mentioned in passing before that one of the good ways to filter mail based on content is to look for suspicious URLs in the message. One way of doing this is to use hostname-based blacklists, such as SURBL, URIBL or DBL. These list domain names that have been seen in spam (and pretty much only spam), and sending email with a listed hostname in it is a quick trip to blocksville at many ISPs.
Spammers, phishers especially, often cycle through domain names quickly in order to avoid the (manually maintained) hostname-based blacklists. They often host them at the same place, though, so if you look up the IP address the hostname resolves to you can use an IP based blacklist to see if the hostname is being used for spam or phishing related email payloads, and use that information to block the email. That’ll work even if the phishers use an entirely new domain for their websites, if it’s still hosted at the same place.
The SBL blacklist is commonly used in this way. It’s manually maintained and fairly hard to get on to, and finding URLs that resolve to addresses listed on the SBL in an email corresponds pretty strongly to the mail being unwanted. The folks who run the SBL are quite aware of this, and will commonly list IP addresses that are being used to host websites advertised in spam even if they never send email.
What happened in this case was that the client was hosting their website with Heroku, a perfectly respectable cloud-based ruby-on-rails web host. But Heroku use just three IP addresses for all their customers. And one of their customers was zapt.in, a URL shortener with a serious spam problem. Zapt.in caused problems for long enough, and didn’t respond to them for long enough, that their IP address was listed on the SBL.
That meant that all of Heroku’s customers were using an IP address listed on the SBL. Which, in turn, meant that any email those customers (or their affiliates or customers or…) sent that used the customers domain would be rejected by ISPs using the SBL-as-a-hostname-blacklist trick – which is a lot of large ISPs.
What can you do to avoid this? The ideal is to not host your website on a shared IP address (or in a /24 that’s littered with spam and phishing sites).
If you can’t do that – you really can’t move your main website to a more reputable host – then your next best option is to not use your main website in any of the email you send. You don’t want to hide the connection (because you don’t want to look like a snowshoe spammer who’s obfuscating their domain ownership), but you want the hostname to be different. A good way to do that is, if your main domain name is example.com and your website is www.example.com, is to use a subdomain for URLs in emails. click.example.com, maybe.
Host that subdomain somewhere else, on an IP address you have a bit more control over – an inexpensive VPS or web hosting provider, and just run a web redirector there that simply sends an http 302 redirect for any http://click.example.com/foo/bar/baz.html to http://example.com/foo/bar/baz.html. And use the click.example.com form of the URL for everything you use in your email – not just links, but also image tags and so on.
What if setting up your own redirector isn’t something you have the resources to do? Sign up for a web redirector or URL shortener service that’ll let you use your own domain name, like bit.ly Pro. That won’t give you as much control, or protection, as running your own redirector but it’s a lot better than running your website on a shared IP address.