Advance-fee fraud (Nigerian 419)

Does this only apply to 419's or to other spam as well? Check the headers of the false negatives, I bet they come from hacked gmail/yahoo accounts. The Commtouch engine has problems with these.

I don't think these fall into that category.  Here's an example, let me know if I've misunderstood or you'd like for me to send examples to someone.

Microsoft Mail Internet Headers Version 2.0
Received: from mail.mydomain.com ([10.1.1.34]) by mydomain.com with Microsoft SMTPSVC(6.0.3790.3959);
 Sat, 6 Sep 2008 12:54:12 -0500
Received: from newglendora.techhosting.com ([216.193.210.232]:57563)
by mail.mydomain.com with esmtps (TLSv1:AES256-SHA:256)
(Exim 4.69)
(envelope-from )
id 1Kc1zs-0005zR-2A
for info@mydomain.com
CTCH-RefID str=0001.0A010205.48C2C3F1.0014,ss=1,fgs=0; Sat, 06 Sep 2008 12:54:57 -0500
Received: from brescy by newglendora.techhosting.com with local (Exim 4.69)
(envelope-from )
id 1Kc1zr-0008D7-EV
for info@mydomain.com; Sat, 06 Sep 2008 10:54:55 -0700
To: info@mydomain.com
Subject: (CONGRATULATIONS)
From: NOKIA LOTTO PROMO U.K 
MIME-Version: 1.0
Content-Type: text/html; charset="utf-8"
Content-Transfer-encoding: 8bit
Reply-To: NOKIA LOTTO PROMO U.K 
Message-ID: 
X-Priority: 1
X-MSmail-Priority: High
X-Mailer: Microsoft Office Outlook, Build 11.0.5510
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1441
Date: Sat, 06 Sep 2008 10:54:55 -0700
X-AntiAbuse: This header was added to track abuse, please include it with any abuse report
X-AntiAbuse: Primary Hostname - newglendora.techhosting.com
X-AntiAbuse: Original Domain - mydomain.com
X-AntiAbuse: Originator/Caller UID/GID - [32069 32071] / [47 12]
X-AntiAbuse: Sender Address Domain - newglendora.techhosting.com
Return-Path: brescy@newglendora.techhosting.com
X-OriginalArrivalTime: 06 Sep 2008 17:54:12.0416 (UTC) FILETIME=[91F4B400:01C91049]