Email Issue - Emails not received when sender uses reply

OK, I have this weird issue that all of the sudden popped up.  It seems to happen most often with international email, but it may not be 100%.

Anyway for certain senders (from OUTSIDE my organization) try to send emails into my organization, they end up in a retry queue for some time, then eventually go into failure.  An NDR is sent to the sender eventually. The NDR is giving a 5.1.1 error code (I had the sender send me the NDR to my gmail account)

I had the sender try to send the exact same email again, but after hitting reply, to delete the recipients address and then type it  in fully manually (no auto-fill).  BAM! The email went through.

I had an idea, since most (possibly all) the issues were coming from international senders.  I had a user who was having similar issues when sending to a company in another country, but only when using reply.  I found that for some reason, when using reply, outlook was using a 'custom' protocol to send the email.  I can't for the life of me find where I saw this, but somewhere under the outgoing message preferences there was a field for protocol, and in it was "CUSTOM" and"MAILTO".  Now I'm aware of what MAILTO is (html).  Once we had the user change this to smtp, or, type the address in manually, it went through.
Who is Participating?
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.

Alan HardistyCo-OwnerCommented:
What is the default email address on the user account for the user(s) with the problem?  Does the email address end with .local?

It might be you have your recipient policy configured incorrectly and this has recently changed.

Have you checked your Recipient Policies to make sure the proper domain is in bold (default)?
Alan HardistyCo-OwnerCommented:
If you like - drop me a test email to alan @ and I will see what you are sending out as.
JamesonJendreasAuthor Commented:
Awesome Alan, I'll be coming from the mydomain domain!

I'll double check those other options, but the default doesn't end in .local, that's for sure.  I've checked through the recipeint policy and haven't seen anything, but I may have to go over it with a fined-toothed-comb
Big Business Goals? Which KPIs Will Help You

The most successful MSPs rely on metrics – known as key performance indicators (KPIs) – for making informed decisions that help their businesses thrive, rather than just survive. This eBook provides an overview of the most important KPIs used by top MSPs.

Alan HardistyCo-OwnerCommented:
Just been greylisted - will wait to see what happens when your server retries.

JamesonJendreasAuthor Commented:
not too sure if it is relevant, but we do have CCMAIL, MS, X400 as well as SMTP addresses for each user (not 100% sure why, this was inherited from my predecessor).
Alan HardistyCo-OwnerCommented:
Okay - you are not sending as .local, so that's not the problem.

The 5.1.1 error is an Unknown User Error - so is the user with the problem a new user?

You have 3 MX records - so are all 3 mail servers configured with ALL the email addresses on yur own server?  It might be that the external senders are not hitting your primary MX record (your own server) and hitting another server and not finding the user.

Does that sound possible?

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
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.