Scanning a compromised Fedora server

This does sound like malicious behaviour, but it's very hard to say exactly what the issue is based on the limited information in your question. If you think your host is compromised, then I recommend your first step should be to pull the host off the network and quarantine it for further analysis. If you don't have the capability in-house to do this analysis, then I recommend you engage a third-party security organisation or consultancy to help you out.

If you don't or can't do this then, I suggest first checking your logs to determine it isn't a mis-configuration, such as being an open relay. Check both the logs on your mail server and your host. Qmail is an excellent package when it comes to logging. Every transaction Qmail undertakes is generally logged by default. You can find some more information on Qmail troubleshooting and logging at: Qmailrocks.org or the Life with qmail troubleshooting FAQ.

The qmail mailing list is also excellent source of information and help. You can find it at http://cr.yp.to/lists.html#qmail. Remember to clearly articulate your problem, post relevant logs and detail your configuration to allow other users to properly assist you.

You can also use tools such as Wireshark or tcpdump to analyse your outgoing network traffic. A Nessus and nmap scan of your host to detect vulnerabilities or unusual ports open is also a good idea. Checking for root kits (tools used to compromise your hosts) using a tool like chkrootkit may also determine if a root kit is running.

But I strongly recommend that this sort of behaviour can often be malicious and the safest course of action, if you can't immediately identify the issue, is to remove the box from the network before it is used to further compromise yours or others' networks.