If I could find a way to filter spam as well as gmail does I would love to back to self-hosting my email. I just can't imagine a time when we'll get anything close to what gmail can do without their huge resources.
But! You can do pretty well at it, too, if you feel like putting in the effort. I host email for some clients, and most of my sysadmin time these days is spent dealing with spam in some fashion or another.
1. Greylisting. Greylisting is fantastic, and the package you're looking for here is sqlgrey. It's easy to use and admin and it has sensible defaults. You can pretty much just drop it in and immediately get an 80% reduction in spam.
2. Use the right MTA stack: currently I think that's Postfix and Dovecot. Postfix and Dovecot go together like ice cream and apple pie. Postfix is far easier to admin and configure than Sendmail, and Dovecot has good support for managesieve, which'll be important in a moment.
3. Install SpamAssassin and AMaViS. Getting it working correctly with Postfix in a multi-domain environment, so that each user can have their own SA settings, is a little bit tricky, but totally worth it. AMaViS by default wants to manage SA's settings. Don't let it.
4. Install the managesieve, password, and sauserprefs plugins. Now you can change your email password, your filters, and your SpamAssassin preferences right from the webmail interface.
5. Configure SpamAssassin to label messages "[SPAM]" (it also sets the X-Spam-Flag header) on junk messages, and then set up a default filter in managesieve to redirect those things to Junk folder. Bam, no missing emails, no cluttered inbox. Use imap on your favorite devices.
6. A couple of extras, like Fail2Ban, will help too. You can modify Fail2Ban to watch your mail.log for frequent attempts at nonexistent user accounts and then iptables those spammers.
As with most things, you can spend as much additional time as you'd like fine tuning this, writing some custom software, and so on. But, the above will get you about 98% of the way to Gmail's level of spam filtering in about a day's worth of work.
No other filtering is applied, no greylisting, no country blocks (I need to be able to communicate with people all over the world), no fail2ban, no nothin'. By keeping the filtering concentrated in one spot I avoid the trap of turning the mail system into a Rube Goldberg machine loaded with unintended consequences.
On average, one or two spammy messages make it through the portcullis per day. I simply dump them in the 'SPAM-it' folder and forget about them. False positives are exceedingly rare, fortunately. On the whole I consider my mail setup to be functional and above all manageable.
Everything needed to implement this is available in Debian. There is a handy Sieve editor available as a plugin to the Roundcube web mail client for those who like to click pretty boxes instead of writing filter scripts.
* don't accept mail for non-existing recipient adresses
* don't accept mail where the sender domain is one of my domains, except when whitelisted manually
* don't accept mail from hosts on the NiXSpam list[1] (unlike some others, NixSpam has pretty reasonable policies with automatic delisting after 12 hours)
These three rules together work pretty well, I get only a handful false negatives every day, and virtually no false positives, even though I publish my real mail address on many places in the web, and even used it in usenet, back in the days.
Next step would be using SpamAssassin, but [2].
[1] http://www.heise.de/ix/NiX-Spam-DNSBL-and-blacklist-for-down...
If I remember correctly they are pretty trigger happy with honeypot email addresses that are pretty easy to find on the internet.
All your competition needs to do is register to your service using the honeypot email addresses and your legitimate email server/domain will be blacklisted on hosts that check NIXSpam.
Direct strangers to reach to you via Twitter.
I'm thinking about turning on greylisting as well, but right now its not needed.