FortiMail with Exchange Server: 550 5.7.1 Relay access denied, 451 and recipient checks

With FortiMail filtering mail for on-premises Exchange, most failures happen at one of three hand-offs: FortiMail delivering to Exchange, FortiMail checking that a recipient exists, and Exchange relaying outbound mail through FortiMail. In this post I'll match the errors on each side to the setting behind them, then show how to configure and prove each hand-off on Exchange Server SE and 2019 (2016 works the same way).

Symptoms#

You'll see one or more of these:

• Outbound messages bounce, and message tracking shows a FAIL event with FortiMail's reply 550 5.7.1 Relay access denied.
• External senders report delays. Their queues show FortiMail answering 451 Try again later, and FortiMail's antispam log has entries like Verify <user@example.com> Failed, return TEMPFAIL.
• Senders get FortiMail NDRs for addresses that exist in Exchange (often aliases or groups), FortiMail's log may show entries like <user@example.com>... User unknown, and Exchange message tracking shows nothing.
• Outbound mail sits in a Retry queue with 441 4.4.1 Error encountered while communicating with primary target IP address.
• FortiMail returns temporary failures and its event log shows Milter (fas_milter): timeout before data read.

Why it happens#

FortiMail runs in one of three operation modes: gateway (your MX points at FortiMail, which relays to Exchange; the usual design and the one this post assumes), transparent (inline, intercepting SMTP to the protected server without an MX change) or server (FortiMail is the mail server itself, so it's not relevant here).

Each protected domain defines where its mail is relayed and how recipients are verified. Fortinet's troubleshooting guide explains the errors:

• Relay permission. Mail to protected domains is relayed automatically, but mail to any other domain (your outbound traffic) is relayed only if the client authenticates or an access control rule allows it. If your Exchange servers aren't covered, they get 550 5.7.1 Relay access denied.
• Recipient verification. When FortiMail can't reach the verification server, it answers 451 and the sender retries. Fortinet also notes that Exchange doesn't reject unknown recipients by default, so SMTP verification against Exchange needs extra setup; it recommends LDAP verification against Active Directory. FortiMail refuses an address the verification source doesn't recognise (Fortinet's knowledge base shows failed verifications logged as User unknown), so an incomplete LDAP query turns real aliases into rejections. Greylisting also returns 451 Try again later to first-time senders, which is expected and clears on retry.
• Scan timeouts. The fas_milter message means antispam scanning didn't finish within four minutes, often because DNSBL or SURBL lookups were slow.
• Connectivity. 441 4.4.1 means Exchange couldn't open or keep an SMTP session with FortiMail: a firewall rule, a wrong smart host name, or FortiMail being down.

How to fix it#

1. Route inbound mail from FortiMail to Exchange#

Protected domains are under Domain & User › Domain › Domain. In gateway mode, set the relay type to Host and the SMTP server to Exchange (or an internal load-balanced name). The public MX points at FortiMail, so a relay type that follows the domain's own MX record would hand mail straight back to FortiMail. Keep a single MX record pointing at FortiMail: a backup MX that points at Exchange lets spam bypass the filter.

On Exchange, give FortiMail its own receive connector (easier to log and tune), and let only FortiMail reach port 25 from outside:

New-ReceiveConnector -Name "Inbound from FortiMail" -Server EX01 -TransportRole FrontendTransport -Custom `
    -Bindings 0.0.0.0:25 -RemoteIPRanges 10.0.5.20,10.0.5.21 -PermissionGroups AnonymousUsers
Set-ReceiveConnector "EX01\Inbound from FortiMail" -ProtocolLoggingLevel Verbose

Keep it anonymous: Externally secured would make Exchange trust every internet message FortiMail relays, so spoofed internal senders resolve to real users.

2. Fix recipient verification#

Use LDAP verification against Active Directory, as Fortinet recommends when Exchange is the mail server. Bind with a service account whose password won't expire unnoticed, and make sure the query matches every address Exchange accepts: primary addresses, aliases in proxyAddresses, groups, mail contacts and mail-enabled public folders. A query that only checks the mail attribute, or a base DN that covers one OU, makes FortiMail reject valid recipients before Exchange ever sees the message. To see which object owns an address FortiMail rejected:

Get-Recipient alias@contoso.com | Format-List Name, RecipientType, PrimarySmtpAddress, EmailAddresses

Think twice before switching to SMTP verification against Exchange. It only works if Exchange refuses unknown addresses at RCPT TO, which is the Recipient Filter agent's job: it answers 550 5.1.1 User unknown for an unknown address and 250 2.1.5 Recipient OK for a real one. Microsoft documents recipient lookup for Edge Transport servers and says you shouldn't configure the Recipient Filter agent on Mailbox servers, because recipient filtering there rejects a whole message when one of several recipients is invalid or blocked. Without it, a Mailbox server accepts any address in your domains during the SMTP session, so SMTP verification can't tell real recipients from made-up ones. If you do run Exchange's own antispam agents behind FortiMail, also set InternalSMTPServers as described in the vendor-neutral checklist linked below.

3. Let Exchange relay outbound mail through FortiMail#

New-SendConnector -Name "Outbound via FortiMail" -Internet -AddressSpaces "*" -DNSRoutingEnabled $false `
    -SmartHosts "fortimail.contoso.com" -SourceTransportServers EX01,EX02

Disable the old internet send connector so it can't compete for the * address space. On FortiMail, add an access control rule that allows relay from your Exchange servers' addresses (or have the connector authenticate), plus an IP-based policy for those addresses with antispam and antivirus profiles. A connection that matches no policy is allowed but not scanned. If 441 4.4.1 persists, run Test-NetConnection fortimail.contoso.com -Port 25 from each source server.

4. Sort out TLS and sender authentication#

Exchange offers STARTTLS with the certificate that matches the receive connector's FQDN. If FortiMail validates certificates, make sure that certificate's name matches the host name FortiMail connects to (see Event ID 12014). To require a validated TLS session on the outbound leg:

Set-SendConnector "Outbound via FortiMail" -RequireTLS $true -TlsAuthLevel DomainValidation -TlsDomain fortimail.contoso.com

Your SPF record must now list FortiMail's public addresses, because that's where outbound mail leaves your network. Exchange Server doesn't DKIM-sign messages itself, so if FortiMail signs (Fortinet's cookbook covers this in Enabling DKIM signing on FortiMail), publish each sending domain's public key in DNS before you switch signing on.

Verify the fix#

Test recipient verification from a host outside your network: in a manual SMTP session to FortiMail, RCPT TO for a made-up address in your domain should be refused (look for a User unknown entry in FortiMail's log), and a real alias should be accepted with a 250 reply. Then trace test messages both ways:

Get-TransportService | Get-MessageTrackingLog -Start (Get-Date).AddMinutes(-30) -Sender test@fabrikam.com |
    Sort-Object Timestamp | Format-Table Timestamp, EventId, Source, ConnectorId, ClientIp, RecipientStatus -AutoSize
Get-Queue | Where-Object DeliveryType -eq SmartHostConnectorDelivery | Format-List Identity, Status, MessageCount, LastError

Good looks like this: inbound RECEIVE events through your FortiMail connector with a FortiMail ClientIp, outbound SEND events through "Outbound via FortiMail" with a 250 reply, and an empty smart host queue. FortiMail's history log should show the same messages, and its antispam log no new TEMPFAIL entries.

Prevent it next time#

• Add a protected domain (or domain association) in FortiMail whenever you add an accepted domain in Exchange, and remove both together.
• Add new Exchange servers and changed NAT addresses to FortiMail's access control rules and IP policies before mail flow moves to them.
• Monitor the LDAP bind account, and keep FortiMail's DNS fast; Fortinet suggests local DNSBL/SURBL servers if milter timeouts persist.
• Use the vendor-neutral checklist in putting any email security gateway in front of Exchange Server, and look up other gateway replies in the gateway rejection codes quick reference.

References#

• Troubleshoot MTA issues (FortiMail Administration Guide)
• Configuring protected domains (FortiMail 7.6.3 Administration Guide)
• Recipient filtering on Edge Transport servers (Microsoft Learn)
• Create a Send connector to route outbound mail through a smart host (Microsoft Learn)