smtp 554 5.7.1 : Relay access denied randomly from outside

we have some problem receiving email from outside.
This is scenario:
- Ms Exchange 2010
- fortimail virtual appliance
- fortigate firewall
we send correctly with SMTP external connector (configured in a right way in SPF record.)
we receive with 3 different mx record, with different priority,  based on 3 different internet connection up and running
internal mail is ok

Some external user often receive a :

This is an automatically generated Delivery Status Notification.      
Delivery to the following recipients was aborted after 61 second(s):

Diagnostic-Code: smtp; 554 5.7.1 : Relay access denied

This happens:
- from different external sender A,B,C... of different domains
- randomly (if A write two times to, one time goes and one time error)
- we rebooted fortimail appliance and internal domain controller for LDAP Auth
- we rebooted ISP connectivity router

Please help, now we don't know how many emails are rejected and this is can be a great problem
Ask me for details, sorry for my english
Really thanks
Mattia MinerviniAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Dr. KlahnPrincipal Software EngineerCommented:
"554 Relay access denied" is normally generated at the receiving MTA, not by your equipment.  It will help us if you can post the complete headers from a couple of bounced email messages so that we can have a look at where this is happening.

Deface any usernames, domain names and IP addresses, but leave everything else intact so that we can see where in the delivery process the error is occurring.
Mattia MinerviniAuthor Commented:
Sorry , only to be clear...
we not receive these emails, sent by outside to our domain, so we are the receiving MTA , no?
In attachment status and bodypart, in yellow info i have deleted
Are you talking about these info?
Dr. KlahnPrincipal Software EngineerCommented:
My policy is to not open Office documents.  There are security issues with macros and other infections.

Could you repost these in Rich Text Format (RTF)?
Problems using Powershell and Active Directory?

Managing Active Directory does not always have to be complicated.  If you are spending more time trying instead of doing, then it's time to look at something else. For nearly 20 years, AD admins around the world have used one tool for day-to-day AD management: Hyena. Discover why

Mattia MinerviniAuthor Commented:
Dr. KlahnPrincipal Software EngineerCommented:
It would appear that there are some fonts on the system that generated this report that are not available on my system.  Still, it's early on yet and I'm sure there will be someone on later who can read it.

RTF file
Mattia MinerviniAuthor Commented:
here in pdf...
David FavorLinux/LXD/WordPress/Hosting SavantCommented:
Better to test + know, than guess.

Here's how I'd test this.

1) Stop 2x instances of your MX listeners.

2) Send your mail.

3) If mail send worked as expected, then start another MX + stop current one.

Likely what you'll find is one MX listener is configured slightly different than the others, which is causing the problem.

If you have only one MX running at a time + send all mail to this known MX... likely you can find problem MX listener faster.
Jamie McKillopIT ManagerCommented:
This is most likely an issue with your firewall configuration. I'm not a networking expert and I'm unsure if it is possible to NAT a single internal IP to multiple external IPs. How exactly are you NAT'ing your email appliance to all three internet connections?

As a first troubleshooting step, I recommend you get on a PC outside your network and telnet to port 25 of each of your MX records. Make sure you are getting a response from your email appliance. My guess is that only one of those MX records is actually getting to your email appliance.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Mattia MinerviniAuthor Commented:
which logic use mx assignment?
i have 3 mx
mx1 priority 1
mx2 priority 4
mx3 priority 5

when email is send to mx2? when mx1 in unavailable, busy, timeout....?
now i'll do these test with mx

just changed ldap server for authentication (appliance use two dc. to exclude problem on one dc, we tried using only a dc for 1 hour, thenother dc for other hour. same problem -> 10 mail from outside, 1 not delivered with relay access denied)
David FavorLinux/LXD/WordPress/Hosting SavantCommented:
There's also an even easier way to test this.

1) Extract all MX records from DNS.

dig site mx

Open in new window

2) Submit an email to all three MX record using SWAKS at slow submission rate.

swaks -tlsc -auth login -s $MX:587 -au $user -ap $pass --from $from -t $to

Open in new window

3) If single (slow) submissions work, then put the above in a tight loop + see if problem arises under load. Doubtful + might be...

while : ; do swaks -tlsc -auth login -s $MX:587 -au $user -ap $pass --from $from -t $to ; done

Open in new window

For $MX value, substitute in 3x MX records returned by the first dig.

Oh... One other thing.

Best run dig against all of your NS records to, just to make sure...

1) All NS servers return exactly the same MX record set.

2) All NS server return exactly the same IP when each MX record is resolved.

Start at the absolute beginning. Imagine DNS is wrong/broken + debug every step.

My guess is this is a DNS problem, rather than mail server config problem, so I'd test DNS closely, if you haven't done this yet.

If you require assistance, post your actual domain name + someone can run some of these tests for you.
Mattia MinerviniAuthor Commented:
Problem exist on 2nd and 3rd mx record.
So on 10 email, 9 goes on 1st mx (up and running) and 1 on 2nd or 3rd (down one for a nat problem, one for a device problem)
so telnetting was a rapid solution
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.