Perhaps the headers of the spam look something like this:
From wdwarren Sat Mar 04 07:07:05 2000
Received: from [10.1.1.1] by hotmail.com (3.2) with ESMTP id
MHotMailBA8A709500C6D820F3D8D8475492505611; Sat Mar 04 07:06:28 2000 Message-ID: <539045@ 169770>
From: wdwarren <wdwarren>
Subject: UNIVERSITY DIPLOMAS (Verifiable)
Date: Sat, 04 Mar 2000 09:45:21 -0400 (EDT)
Content-Type: TEXT/HTML; charset="US-ASCII"
Where [10.1.1.1] is your server. Note that there are no "received" lines added by your server - or if there are additional received lines, they may look forged or otherwise inconsistant with lines added normally by your mailserver.
This situation is quite common. You may have a user running a dedicated spam sending program (ratware) to send directly from your server. These programs do not use any mailserver facilities on your server - specifically to avoid detection. They are usually named something innocuous like "mailform.pl" or "guestbook.exe". You may also have another exploitable service running on your server which is being exploited by the spammer (see below).
Ideally, you should filter port 25-outbound from this machine and force everyone who uses it legitimately to connect to another, seperate server to send their mail:
[user account server] -> [sendmail on remote mail server] -> [recipient's server]
.. instead of what's happening now:
[user account server] -> [recipient's server]
You must stop these direct connections with a filter and then poke a hole in the filter for only your one, dedicated mail server which should reside on a different server/IP. So applications running on the user's server can only connect to your mailserver via port 25. Of course, they can still send spam, but at least your mailserver will keep a record of it in this configuration.
Alternately, you can solve the problem in the whack-a-mole style: Don't fix the general problem, but sit around and wait for the spamming user to strike. When the spam is being sent (usually late at night or on weekends), you will see the program running (use 'top' or 'ps ax' under unix) and you will also see multiple outbound SMTP connections (use 'netstat -n | grep :25' under unix).
See other FAQ sections for more information on other exploits and fixes (HTTP and SOCKS proxies, etc.).
[Append to This Answer]