6 May 10 19:02
Given that you have run tests against your system to show that it is not an open relay, there are two things to do.
1 - look VERY closely at your logs. You should have receipt of every message that leaves your system.
2 - review the FULL headers of the emails. I would even say post one here. This is a good, reputable forum with a lot of people who are very knowledgeable and helpful.
To the best of my knowledge, it is difficult to fully spoof or conceal the IP addresses in the email chain because the protocols work on bi-directional communications. What is sometimes done, is that erroneous information is pre-pended to the start of the headers to make it look like the messages originate from a fake location.
Another possibility, and this is why I say post the FULL header is that the RCPT TO and FROM fields in the SMTP, which are what show up in the email ARE easily spoofed. You may be having issues with this.
Here is an example that I sent to myself from hotmail, lets analyze it:
Received: from localhost (localhost [127.0.0.1])
by noway2.thruhere.net (Postfix) with ESMTP id BDE568D9
for <firstname.lastname@example.org>; Thu, 6 May 2010 18:48:17 -0400 (EDT)
X-Virus-Scanned: Debian amavisd-new at noway2.thruhere.net
X-Spam-Status: No, score=3.548 tagged_above=2 required=5.01
RCVD_IN_SORBS_WEB=1.117, SPF_PASS=-0.001] autolearn=no
Received: from noway2.thruhere.net ([127.0.0.1])
by localhost (noway2.thruhere.net [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id IWu+9XIkdSfr for <email@example.com>;
Thu, 6 May 2010 18:48:16 -0400 (EDT)
X-Greylist: delayed 60 seconds by postgrey-1.32 at server; Thu, 06 May 2010 18:48:16 EDT
Received: from snt0-omc2-s4.snt0.hotmail.com (snt0-omc2-s4.snt0.hotmail.com [126.96.36.199])
by noway2.thruhere.net (Postfix) with ESMTP id 7C9FB7F7
for <firstname.lastname@example.org>; Thu, 6 May 2010 18:48:16 -0400 (EDT)
Received: from SNT127-W51 ([188.8.131.52]) by snt0-omc2-s4.snt0.hotmail.com with Microsoft SMTPSVC(6.0.3790.4675);
Thu, 6 May 2010 15:47:16 -0700
From: Matt Flyer <email@example.com>
Subject: RE: example
Date: Thu, 6 May 2010 18:47:16 -04
1) the originating IP: 184.108.40.206. We can do a lookup on this and see that it is m2b5e36d0.tmodns.net. I am not sure about this one. It is owned by markmonitor.com
2) Received: from SNT127-W51 ([220.127.116.11]) by snt0-omc2-s4.snt0.hotmail.com with Microsoft SMTPSVC(6.0.3790.4675); From this we see if we trace the first IP we don't get full resolution, but it is refered to NS4.MSFT.NET.
3) we see that it passed through snt0-omc2-s4.snt0.hotmail.com.from the IP 18.104.22.168, which was the last hop before arriving at my server.
From there we can see that it passed through a couple of scans on my server (localhost) before being greylisted and then delivered.
You should be able to use information like this to trace the path. Keep in mind, it may not have originated at the first IP.