You might also look at the results of netstat -tpan and look for incoming and outgoing connections on port 25 (the SMTP port). The -p argument to netstat will tell you which process is responsible for the connection. Note, if your server has been root compromised, netstat may not give accurate results, but it's still useful just to have a look and see what you can find.

Also, a high connection rate should be chewing a fair amount of CPU -- does top show anything out of the ordinary?

About 20% of the ports on netstat -tpan would be port 25. Is that a lot? I would expect mail and port 80 to be the highest, which they are.

There is nothing on top that uses a higher than normal amount of CPU, the normal ones there are mysql httpd etc. Although I did see "spamd" a few times.

How many total outgoing port 25 connections do you have? if this machine isn't expected to be handling a lot of mail traffic then yes, that might be a lot. It's hard to say though because no one here knows the normal mail load for the box (this is why it's important to monitor this sort of thing before there are any problems so there's a baseline to compare against).

Did you see what processes were putting out the port 25 connections? If you have had a Web application exploited it's entirely possible that an httpd process could be doing it. This is becoming increasingly common. You need to check these things and look for processes that are doing things they're not supposed to be.

And yes, definitely do ask for the mail with full headers from the site making the complaint.

I see 13 using port 25. They're all either exim or just blank (a dash).

And yeah, I already asked for the emails w/ full headers before.