I use Outlook and I've found Cloudmark Spamnet to be very effective. It is not rulebased so you will never encounter the problems you described. When you download your mail Spamnet creates a key depending on the contents, then checks in an onine database if that specific key has been marked as spam. If yes, then move/delete/whatever, if not, leave it be. Sometimes you get spams that aren't registered, then you can click a "block" button and the key will be registered at Cloudmark as spam so other users don't have to see it. There are ofcourse some threshold but I don't know how big it is. I think it is pretty safe.
Too bad it is only for Outlook...
http://www.cloudmark.com/products/

Interesting. There's also some variant of SpamAssassin for Outlook I think. At work we're currently on Lotus Notes (and I've only been discovered by a couple of random nigerian "princes" and "bankers" so far) but when we more to Outlook I'll look into it..

Hmm ... I expect to get spam from any email address I publish on a webpage, ever. I keep various email addresses for that. If someone contacts me from an address I have published online, I expect them not to mind if it takes me a little longer to reply. That's the nature of the game, and I'm not in it for commercial reasons.

I get occasional spam from a specific IT recruitment company to my work address, which I find interesting. I can't think how they believe a Software Design Authority has recruitment needs, never mind knowing who I am, but again my work address is public. I suspect this is the best area for spam-blocking email clients to target.

If I get spam at a personal address, that means someone has CCed me in an extremely careless fashion, which is mildly irritating, or published my email address on a webpage, which is unforgiveable. It happens so rarely that I have never encountered it so far. I believe I would discontinue the address and give the next one out more carefully, if that were to happen.

If I sign up for something online with my address, I'll probably use theirsite@mydomain.com. I click each of those "don't email me" boxes judiciously, and I'm (almost) prepared to get legal on them if they breach their privacy agreements, just because it would give me a sadistic sense of pleasure.

In short, it's caveat emptor with regard to giving out your email addresses, and I think that antispam software is largely after the fact for personal usage, although it has its uses for commercial addresses.

I use bayesian spam filter for Outlook SpamBully from http://www.spambully.com