[detritus]

As someone who's had his entirely legitimate, wholly none-spamming email accounts blacklisted (numerous times) because he used the same shared server as someone less than saintly, I can attest that this is actually a genuine and existant concern.

Sure, it's 'easy' to get around, by throwing more money and complexity at the problem, but it isn't some made up tale.

[ryandrake]

I would not use a shared server for E-mail hosting, for this exact reason. Even if you are the only person on the IP, you need to watch out your first couple of months because the IP you have could have been misused in the past. If you find your new host’s IP on a blacklist, request a new IP from your provider.