I'm looking around for a spam filtering service that operates in the model where your domain name points to their MX servers which then deliver filtered or marked mail on to your own MX server(s). But unlike services such as Postini, I'm looking for one that charges by volume of good mail, not by user. I've got some feedback mechanisms going where usernames are dynamic, so doing pricing by user can't function correctly.

The current setup has Postfix, Amavis, and ClamAV, with bits of my own code. It has problems both with false positives and false negatives.

Have you looked into Postgrey ?

I might if I don't find a suitable offsite service.