Hmmm... where to start.

Your Exchange server doesn't make outbound SMTP connections to other email servers FROM port 25, it makes those outbound connections TO port 25. This is the way all TCP\IP hosts operate regardless of the service in question (for the most part, but for this argument consider this to be the case). Exchange uses a local port in the ephemeral port range as it's outgoing port and it connects to another email server on that servers' port 25. This works in reverse when other email servers connect to your Exchange server to send you email, the other server connects from one of it's ephemeral ports to port 25 on your Exchange server.

Why do you think the firewall is relevant to this problem? When the firewall failed did you not have a replacement firewall in place? What was protecting your network while you waited for the new firewall?

If any of your workstations are infected with malware then they're at risk for sending spam through the Exchange server via MAPI or SMTP (depending on how the workstations and the Exchange server are configured), or from themselves.

Merely having a firewall in front of your Exchange server doesn't have anything to do with whether or not your outbound mail will be flagged as Spam or whether or not your Exchange servers' outbound ip address will be blacklisted. External email servers have no way of detecting whether or not your Exchange server is behind a firewall. A firewall may reduce the likelihood of being blacklisted by restricting outbound SMTP traffic to just that from the Exchange server, which presumably is not being used as a relay.

Your first tcpdump shows the TCP session information for what is presumably an SMTP communication session but gives you no information regarding that SMTP session and is therefore almost worthless in troubleshooting your problem.

Your second tcpdump doesn't show any SMTP connection that I could find and is therefore worthless in troubleshooting your problem.

All that being said, here are a couple of pointers:

Make sure your Exchange servers outbound greeting matches the FQDN for your public MX record.

Make sure to set up a PTR record in your public DNS for the FQDN of the Exchange server.

Make sure to set up an SPF record in your public DNS.

Restrict all outbound communication TO port 25 for all internal hosts except your Exchange server.

None of these are guaranteed to keep you off of the blacklists, but they're helpful in that regard.

As a final note, enable SMTP logging on your Exchange server so that you'll have a log record of all inbound and outbound SMTP sessions. This is invaluable in troubleshooting SMTP problems.

To defeat your enemy, you must know your enemy.

What is spam?

For our purposes, spam is any unsolicited bulk electronic message. Spam these days is intended to lure unsuspecting users into visiting a (usually shady) web site where they will be asked to buy products, or have malware delivered to their computers, or both. Some spam will deliver malware directly.

It may surprise you to learn that the first spam was sent in 1864. It was an advertisement for dental services, sent via Western Union telegram. The word itself is a reference to a scene in Monty Python's Flying Circus.

Spam, in this case, does not refer to mailing list traffic a user subscribed to, even if they changed their minds later (or forgot about it) but have not actually unsubscribed yet.

Why is spam a problem?

Spam is a problem because it works for the spammers. Spam typically generates more than enough sales (or malware delivery, or both) to cover the costs -- to the spammer -- of sending it. The spammer does not consider the costs to the recipient, you and your users. Even when a tiny minority of users receiving spam respond to it, it's enough.

So you get to pay the bills for bandwidth, servers, and administrator time to deal with incoming spam.

We block spam for these reasons: we don't want to see it, to reduce our costs of handling email, and to make spamming more expensive for the spammers.

How does spam work?

Spam typically is delivered in different ways from normal, legitimate email.

Spammers almost always want to obscure the origin of the email, so a typical spam will contain fake header information. The From: address is usually fake. Some spam includes fake Received: lines in an attempt to disguise the trail. A lot of spam is delivered via open SMTP relays, open proxy servers and botnets. All of these methods make it more difficult to determine who originated the spam.

Once in the user's inbox, the purpose of the spam is to entice the user to visit the advertised web site. There, the user will be enticed to make a purchase, or the site will attempt to install malware on the user's computer, or both. Or, the spam will ask the user to open an attachment which contains malware.

How do I stop spam?

As a system administrator of a mail server, you will configure your mail server and domain to make it more difficult for spammers to deliver their spam to your users.

I will be covering issues specifically focused on spam and may skip over things not directly related to spam (such as encryption).

Don't run an open relay

The big mail server sin is to run an open relay, a SMTP server which will accept mail for any destination and deliver it onward. Spammers love open relays because they virtually guarantee delivery. They take on the load of delivering messages (and retrying!) while the spammer does something else. They make spamming cheap.

Open relays also contribute to the problem of backscatter. These are messages which were accepted by the relay but then found to be undeliverable. The open relay will then send a bounce message to the From: address which contains a copy of the spam.

• Configure your mail server to accept incoming mail on port 25 only for your own domain(s). For most mail servers, this is the default behavior, but you at least need to tell the mail server what your domains are.
• Test your system by sending your SMTP server a mail from outside your network where both the From: and To: addresses are not within your domain. The message should be rejected. (Or, use an online service like MX Toolbox to perform the test, but be aware that some online services will submit your IP address to blacklists if your mail server fails the test.)

Reject anything that looks too suspicious

Various misconfigurations and errors can be a tip-off that an incoming message is likely to be spam or otherwise illegitimate.

• Mark as spam or reject messages for which the IP address has no reverse DNS (PTR record). Treat the lack of a PTR record more harshly for IPv4 connections than for IPv6 connections, as many IPv6 addresses do not yet have reverse DNS, and may not for several years, until DNS server software is better able to handle these potentially very large zones.
• Reject messages for which the domain name in the sender or recipient addresses does not exist.
• Reject messages which do not use fully qualified domain names for the sender or recipient domains, unless they originate within your domain and are meant to be delivered within your domain (e.g. monitoring services).
• Reject connections where the other end does not send a HELO/EHLO.
• Reject connections where the HELO/EHLO is:
  • not a fully qualified domain name and not an IP address
  • blatantly wrong (e.g. your own IP address space)
• Reject connections which use pipelining without being authorized to do so.

Authenticate your users

Mail arriving at your servers should be thought of in terms of inbound mail and outbound mail. Inbound mail is any mail arriving at your SMTP server which is ultimately destined for your domain; outbound mail is any mail arriving at your SMTP server which will be transferred elsewhere before being delivered (eg. it's going to another domain). Inbound mail can be handled by your spam filters, and may come from anywhere but must always be destined for your users. This mail can't be authenticated, because it is not possible to give credentials to every site which might send you mail.

Outbound mail, that is, mail which will be relayed, must be authenticated. This is the case whether it comes from the Internet or from inside your network (though you should restrict the IP address ranges allowed to use your mailserver if operationally possible); this is because spambots might be running inside your network. So, configure your SMTP server such that mail bound for other networks will be dropped (relay access will be denied) unless that mail is authenticated. Better still, use separate mail servers for inbound and outbound mail, allow no relaying at all for the inbound ones, and allow no unauthenticated access to the outbound ones.

If your software allows this, you should also filter messages according to the authenticated user; if the from address of the mail does not match the user who authenticated, it should be rejected. Do not silently update the from address; the user should be aware of the configuration error.

You should also log the username which is used to send mail, or add an identifying header to it. This way, if abuse does occur, you have evidence and know which account was used to do it. This allows you to isolate compromised accounts and problem users, and is especially valuable for shared hosting providers.

Filter traffic

You want to be certain that mail leaving your network is actually being sent by your (authenticated) users, not by bots or people from outside. The specifics of how you do this depend on exactly what kind of system you are administering.

Generally, blocking egress traffic on ports 25, 465, and 587 (SMTP, SMTP/SSL, and Submission) for everything but your outbound mailservers is a good idea if you are a corporate network. This is so that malware-running bots on your network cannot send spam from your network either to open relays on the Internet or directly to the final MTA for an address.

Hotspots are a special case because legitimate mail from them originates from many different domains, but (because of SPF, among other things) a "forced" mailserver is inappropriate and users should be using their own domain's SMTP server to submit mail. This case is much harder, but using a specific public IP or IP range for Internet traffic from these hosts (to protect your site's reputation), throttling SMTP traffic, and deep packet inspection are solutions to consider.

Historically, spambots have issued spam mainly on port 25, but nothing prevents them from using port 587 for the same purpose, so changing the port used for inbound mail is of dubious value. However, using port 587 for mail submission is recommended by RFC 2476, and allows for a separation between mail submission (to the first MTA) and mail transfer (between MTAs) where that is not obvious from network topology; if you require such separation, you should do this.

If you are an ISP, VPS host, colocation provider, or similar, or are providing a hotspot for use by visitors, blocking egress SMTP traffic can be problematic for users who are sending mail using their own domains. In all cases except a public hotspot, you should require users who need outbound SMTP access because they are running a mailserver to specifically request it. Let them know that abuse complaints will ultimately result in that access being terminated to protect your reputation.

Dynamic IPs, and those used for virtual desktop infrastructure, should never have outbound SMTP access except to the specific mailserver those nodes are expected to use. These types of IPs should also appear on blacklists and you should not attempt to build reputation for them. This is because they are extremely unlikely to be running a legitimate MTA.

Consider using SpamAssassin

SpamAssassin is a mail filter which can be used to identify spam based on the message headers and content. It uses a rules-based scoring system to determine the likelihood that a message is spam. The higher the score, the more likely the message is spam.

SpamAssassin also has a Bayesian engine which can analyze spam and ham (legitimate email) samples fed back into it.

Best practice for SpamAssassin is not to reject the mail, but to put it in a Junk or Spam folder. MUAs (mail user agents) such as Outlook and Thunderbird can be set up to recognize the headers that SpamAssassin adds to email messages and to file them appropriately. False positives can and do happen, and while they're rare, when it happens to the CEO, you will hear about it. That conversation will go much better if the message was simply delivered to the Junk folder rather than rejected outright.

SpamAssassin is almost one-of-a-kind, though a few alternatives exist.

• Install SpamAssassin and configure automatic update for its rules using sa-update.
• Consider using custom rules where appropriate.
• Consider setting up Bayesian filtering.

Consider using DNS-based blackhole lists and reputation services

DNSBLs (formerly known as RBLs, or realtime blackhole lists) provide lists of IP addresses associated with spam or other malicious activity. These are run by independent third parties based on their own criteria, so research carefully whether the listing and delisting criteria used by a DNSBL is compatible with your organization's need to receive email. For instance, a few DNSBLs have draconian delisting policies which make it very difficult for someone who was accidentally listed to be removed. Others automatically delist after the IP address has not sent spam for a period of time, which is safer. Most DNSBLs are free to use.

Reputation services are similar, but claim to provide better results by analyzing more data relevant to any given IP address. Most reputation services require a subscription payment or hardware purchase or both.

There are dozens of DNSBLs and reputation services available, though some of the better known and useful ones I use and recommend are:

Conservative lists:

• Spamhaus ZEN
• Barracuda Reputation Database (no purchase necessary)
• SpamCop

Aggressive lists:

• UCEPROTECT
• Backscatterer

As mentioned before, many dozens of others are available and may suit your needs. One of my favorite tricks is to look up the IP address which delivered a spam that got through against multiple DNSBLs to see which of them would have rejected it.

• For each DNSBL and reputation service, examine its policies for listing and delisting of IP addresses and determine whether these are compatible with your organization's needs.
• Add the DNSBL to your SMTP server when you have decided it is appropriate to use that service.
• Consider assigning each DNSBL a score and configuring it into SpamAssassin rather than your SMTP server. This reduces the impact of a false positive; such a message would be delivered (possibly to Junk/Spam) instead of bounced. The tradeoff is that you will deliver a lot of spam.
• Or, reject outright when the IP address is on one of the more conservative lists, and configure the more aggressive lists in SpamAssassin.

Use SPF

SPF (Sender Policy Framework; RFC 4408 and RFC 6652) is a means to prevent email address spoofing by declaring which Internet hosts are authorized to deliver mail for a given domain name.

• Configure your DNS to declare an SPF record with your authorized outgoing mail servers and -all to reject all others.
• Configure your mail server to check the SPF records of incoming mail, if they exist, and reject mail which fails SPF validation. Skip this check if the domain does not have SPF records.

Investigate DKIM

DKIM (DomainKeys Identified Mail; RFC 6376) is a method of embedding digital signatures in mail messages which can be verified using public keys published in the DNS. It is patent-encumbered in the US, which has slowed its adoption. DKIM signatures can also break if a message is modified in transit (e.g. SMTP servers occasionally may repack MIME messages).

• Consider signing your outgoing mail with DKIM signatures, but be aware that the signatures may not always verify correctly even on legitimate mail.

Consider using greylisting

Greylisting is a technique where the SMTP server issues a temporary rejection for an incoming message, rather than a permanent rejection. When the delivery is retried in a few minutes or hours, the SMTP server will then accept the message.

Greylisting can stop some spam software which is not robust enough to differentiate between temporary and permanent rejections, but does not help with spam that was sent to an open relay or with more robust spam software. It also introduces delivery delays which users may not always tolerate.

• Consider using greylisting only in extreme cases, since it is highly disruptive to legitimate email traffic.

Consider using nolisting

Nolisting is a method of configuring your MX records such that the highest priority (lowest preference number) record does not have a running SMTP server. This relies on the fact that a lot of spam software will only try the first MX record, while legitimate SMTP servers try all MX records in ascending order of preference. Some spam software also attempts to send directly to the lowest priority (highest preference number) MX record in violation of RFC 5321, so that could also be set to an IP address without an SMTP server. This is reported to be safe, though as with anything, you should test carefully first.

• Consider setting your highest-priority MX record to point to a host which does not answer on port 25.
• Consider setting your lowest-priority MX record to point to a host which does not answer on port 25.

Consider a spam filtering appliance

Place a spam filtering appliance such as Cisco IronPort or Barracuda Spam & Virus Firewall (or other similar appliances) in front of your existing SMTP server to take much of the work out of reducing the spam you receive. These appliances are pre-configured with DNSBLs, reputation services, Bayesian filters and the other features I've covered, and are updated regularly by their manufacturers.

• Research spam filtering appliance hardware and subscription costs.

Consider hosted email services

If it's all too much for you (or your overworked IT staff) you can always have a third party service provider handle your email for you. Services such as Google's Postini, Symantec MessageLabs Email Security (or others) will filter messages for you. Some of these services can also handle regulatory and legal requirements.

• Research hosted email service subscription costs.

What guidance should sysadmins give to end users regarding fighting spam?

The absolute #1 thing that end users should do to fight spam is:

• DO NOT RESPOND TO THE SPAM.

  If it looks funny, don't click the website link and don't open the attachment. No matter how attractive the offer seems. That viagra isn't that cheap, you aren't really going to get naked pictures of anybody, and there is no $15 million dollars in Nigeria or elsewhere except for the money taken from people who did respond to the spam.

• If you see a spam message, mark it as Junk or Spam depending on your mail client.

• DO NOT mark a message as Junk/Spam if you actually signed up to receive the messages and just want to stop receiving them. Instead, unsubscribe from the mailing list using the unsubscribe method provided.

• Check your Junk/Spam folder regularly to see if any legitimate messages got through. Mark these as Not Junk/Not Spam and add the sender to your contacts to prevent their messages from being marked as spam in the future.