Sending email to .mil addresses

That's not the correct MX for navy.mil.

Please check your DNS settings or records.

I guess I'm confused... MXtoolbox returns mx:navy.mil as:

156.112.250.0
156.112.250.10
205.85.33.247
205.85.49.228
205.85.41.166 (the one in the error)

There are about 25 servers having priority over the one you're trying. I think the military maintaining 25 servers, and forgetting to check up on server 26th, is nothing to write home about. Please use the priorities as advertised. Not adhering to priorities, leaves you to cases like these.

Tip, here are 16 servers that work:

156.112.250.6
156.112.250.8
156.112.250.0
156.112.250.2
156.112.250.15
156.112.250.1
156.112.250.4
156.112.250.3
156.112.250.7
156.112.250.14
156.112.250.13
156.112.250.10
156.112.250.9
156.112.250.5
156.112.250.11
156.112.250.1

Not gonna lie, you lost me.

How do you setup DNS priority for Exchange so it will only connect to particular records?

Set up a trustworthy DNS server or forwarder.

okay it seems to me the remote server you are trying to reach is not in service at the moment

Remote Server at navy.mil (205.85.41.166) returned '400 4.4.7 Message delayed' - because you have a TTL to retry

Remote Server at navy.mil (205.85.41.166) returned '451 4.4.0 Primary target IP address responded with: "421 4.4.1 Connection timed out." Attempted failover to alternate host, but that did not succeed.

It is telling you the server is dead, not online.

Thanks, Hemil.  I guess we somehow picked up old/low priority DNS records for navy.mil and I don't know how to tell Exchange to look elsewhere.  I'm trying to figure that out at the moment!  I do day-to-day Exchange admin stuff but I'm certainly no Exchange guru.  Email and the network are working perfectly for everything else.

Hi Justin,

Based upon your comment, seemingly your problem was related to MX records. It's Navy.mil your exchange domain? because  I thought you were referring sending emails to navy.mil.

There's no way for you to tell the exchange where to go. DNS is the one who tells your domain.email where to go via MX records.
What you can do it's set priority/value on each MX record adding their IP.

For example

10: 1.1.1.1
11: 2.2.2.2
12: 3.3.3.3

What you are saying is, hey if "1.1.1.1" is not responding go to my next value and so forth.

Hope it helps,

Navy.mil is not my exchange domain and, yes, I'm trying to send to navy.mil.  Sorry, I have multiple things going on so I may not have responded as clearly as I should have.  I've never had to setup MX records in DNS for priorities so that's what I'm currently looking up.

Again, appreciate the help.

As I said, no need to set up records if you have a trustworthy DNS forwarder. Enough to chose from (like Google's 8.8.8.8)

Do you have a PTR record for your exchange server public IP. 

Example:
                     
(A) lookup for example.domain.com resolves to Our IP(x.x.x.x)
(PTR) lookup for Our IP(x.x.x.x) reverses to example.domain.com

So on Friday I cleared the caches across our internal DNS servers and double-checked our forwarders which, on all internal DNS servers, point to 8.8.8.8 and 8.8.4.4 (Google).  Then I sent email to a couple navy.mil addresses.  Both timed out Sunday (~48 hours).

Errors this time were-

2/2/2020 9:52:00 PM - Remote Server at navy.mil (205.85.33.247) returned '451 4.4.0 Primary target IP address responded with: "421 4.4.1 Connection timed out."

2/2/2020 9:59:01 PM - Remote Server at navy.mil (205.85.41.166) returned '451 4.4.0 Primary target IP address responded with: "421 4.4.1 Connection timed out."

So after clearing all of the DNS caches available to me, we still pull, from Google, IPs with lower preferences.

How do I tell my servers to use those IPs with higher preference?

Hey dude,

This problem should not be so difficult to understand.

Your forwarders are just fine. The problem must be on the navy.mil endpoint. Either service is down or your IP/domain has been blacklisted on their end.

DNS works like this.

If you are not navy.mil, your DNS will look-up outside of your local DNS using your forwarders, your forwarders will look for your root or TLD as unless you have it on the cache.
Also, you do not need to worry about preferences, email DNS works round-robin - meaning if one IP goes timed out it will move with the next one, yada yada...

Something that you could try is, use your Gmail account and send an email to navy.mil for testing if you get a bounce-back then, contact the hostmaster or try to contact the administrator for that matter. That's what you should do if your company tries to reach the US navy.

I sincerely appreciate all of the feedback.  I never thought to flush our internal DNS caches last week but considering it still doesn't work I don't think it's something I have the power to fix.

The last message was beating a dead horse so I can show this thread to a higher-up and honestly say "I don't think this is a problem on our side."  Helps to have someone agreeing with me on a site like this.  We're still waiting to hear back from Tier2/3 on the military side so we can get this squared away.

Again, appreciate the help guys.

You should not only clear DNS cache on your DNS servers, ALSO on the Exchange server! Also, do some traffic analysis on both the Exchange and DNS server, to see the DNS requests and answers.

Still in worst case, yes, manage DNS records on your own DNS server until you've figured out the problem.