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.