Being a hosted service, we have a number of customers who share an outbound IP range.  If one of those customers starts to misbehave, their actions can affect everyone else.

We've lot about outbound spam this past year.  We've implemented a number of solutions and incrementally have started to tighten the screws in what we will allow customers to send out without any interference from our side.  We have discovered that the following about outbound spam from customers:

1. The techniques used for inbound filtering don't carry over quite as well for outbound mail scanning.  The false positives are higher for outbound than they are for inbound.  This remains a puzzle.
   
   
2. The spam problem is in reverse; for inbound mail, it's mostly spam with some legit mail.  For outbound, it's mostly legit mail with some spam.  Detecting spikes in mail doesn't work very well because the day-to-day data is so noisy, a blip in traffic from one customer doesn't stand out in the overall scheme of things.

Going from the above, we've had to deconstruct the problem down into a series of smaller problems.  In roughly the following order of difficulty, here are the scenarios when dealing with outbound "spammers":

1. Outbound spam that we detect from spoofed senders 
   
   When a customer sends spam from a domain that we don't know about (ie, *@yahoo.com, *@paypal.com, etc), we catch and handle this case.  It is permissible for customers to send mail as sending domains that they have not registered with us but we will treat that mail differently if they do and we detect it as spam.
   
   
2. Outbound spam that we miss, from spoofed senders
   
   This is somewhat similar to the above, except that our normal filters miss the message and don't detect it as spam.  This doesn't occur often, but it happens enough to be a nuisance.  To that end, we decided to treat this mail differently as well and apply some heuristics to it.  Borderline mail gets nudged over the spam threshold if it's outbound and the sender isn't registered.  We don't block it, but we do detect it and treat it differently.
   
   
3. Outbound spam that we detect from good senders
   
   Originally, we thought we'd give our customers a break.  If you are sending mail from a domain that is registered with us, we'll treat you well.  You're doing something you are supposed to do - send mail from presumably locked down accounts.  Well, as it turns out, it only takes one bad apple to ruin it for everyone in that domain.  Users get their accounts compromised all the time (and it's a different user each week).  So, outbound spam from supposedly well-behaved domains is a third case that must be handled.
   
   
4. Outbound mail that isn't spam but is still getting us blacklisted
   
   This is the most difficult case.  When users do something that is legal according to SMTP but considered bad practice in the real world, that's a problem.  We recently had a user send out a bunch of mail using a domain that had no A-record (ie, test@example.domain.local).  It looked like an admin or programmer or something had an automated report sending a whole pile of mail to his home ISP account (hmm, how many of us have done that?).  Well, guess what?  That ISP detected that sending domain didn't exist and throttled our outbound IPs.  Sending without an A-record isn't illegal, but it is bad form. 
   
   Our filters did not say that the message was spam (and it wasn't).  But someone else's filters said that doing stuff like that is enough to block our IPs.  It ended up hurting us because our filters didn't detect it, and that's the case that, in my opinion, is the most difficult one to solve.  I avoid FPs like the plague, and I think that this was a case of an FP.

We started off with a liberal implementation of outbound spam filtering.  Over time we have slowly and incrementally started clamping down even more and I suspect that we will get to the point where we are very conservative in what we send out.  I don't particularly like that approach but I guess that's the reality of where it's headed.