@jpope: it *really* depends on where you live. If you’re in the US, well… good luck. Maybe sonic.net as suggested above. But if you live in Europe, you might really have better chances. In France, if you take "Free SAS" you’re safe (or, even better, you go to a non-for-profit community ISP, check out ffdn.org for one near you).

But as I said, for self hosting email and other things, the hardest part is going to be the ISP, not the software.

@Blaise Alleyne: the spam problem is twofold:

 - have good protection against getting spam
 - have good options to make sure email you send is not marked as spam by others (esp. Google…)

So it’s much more complicated than just SpamAssassin and Postgrey…