Guys - For some reason when someone from a conus.army.mil or other
domain try and send email to internal users, the sender gets the
following error:

The following message to <u...@mydomain.com> was undeliverable.
The reason for the problem:
5.1.0 - Unknown address error 501-'<external.example.com>:
Helo command rejected: Host not found'

When I check the email server I see the following in /var/log/maillog:

Oct 22 10:00:26 mail postfix/smtpd[26562]: NOQUEUE: reject: RCPT from
ddcoavsgw001.conus.army.mil[143.85.199.17]: 501
<ddcoavsgwhub001.conus.army.mil>: Helo command rejected: Host not
found; from=<u...@us.army.mil> to=<u...@mydomain.com> proto=ESMTP
helo=<ddcoavsgwhub001.conus.army.mil>

Can anyone please explain to me why this emails are being rejected by
my email server?

I am able to receive email from other domains like gmail and
us.army.mil.

As it says.. because that host can't be found.

How come they can send email to my GMail or other web based email utility and it works but when they send to my email server, it fails...

Not to mention they do receive email from us however when they reply or send back to mydomain.com, that is where we have problems.

Because your mail server is configured to reject mail from other mail servers that open their HELO with a domain that can't be found. Post the output of postconf -n.

Is that normal to reject mail from mail serves that open their HELO with a domain that can't be found? Should I change this setting?

[root@mail ~]# postconf -n
alias_database = hash:/etc/postfix/aliases, hash:/etc/postfix/aliases.ctia, hash:/etc/mailman/aliases
alias_maps = hash:/etc/postfix/aliases, hash:/etc/mailman/aliases
biff = no
broken_sasl_auth_clients = yes
command_directory = /usr/sbin
command_time_limit = 1400
config_directory = /etc/postfix
content_filter = smtp-amavis:[127.0.0.1]:10024
daemon_directory = /usr/libexec/postfix
daemon_timeout = 47000
debug_peer_level = 2
default_destination_concurrency_limit = 500
default_destination_recipient_limit = 1000
disable_vrfy_command = yes
header_checks = regexp:/etc/postfix/header_checks
home_mailbox = Maildir/
html_directory = no
inet_interfaces = all
local_recipient_maps =
luser_relay = admin+$local
mail_owner = postfix
mailbox_size_limit = 40000000
mailq_path = /usr/bin/mailq.postfix
manpage_directory = /usr/share/man
max_idle = 175
maximal_backoff_time = 2000s
message_size_limit = 10240000
mime_header_checks = regexp:/etc/postfix/mime_header_checks.regexp
mydestination = $mydomain, $myhostname, localhost.$mydomain, localhost
mydomain = ideorlando.org
myhostname = mail.ideorlando.org
mynetworks = $config_directory/mynetworks
mynetworks_style = host
myorigin = $mydomain
newaliases_path = /usr/bin/newaliases.postfix
proxy_interfaces = 216.242.104.130
qmgr_message_active_limit = 1500
queue_directory = /var/spool/postfix
queue_run_delay = 500s
sendmail_path = /usr/sbin/sendmail.postfix
setgid_group = postdrop
smtp_data_init_timeout = 400s
smtp_data_xfer_timeout = 400s
smtp_helo_timeout = 400s
smtp_mail_timeout = 400s
smtp_quit_timeout = 400s
smtp_rcpt_timeout = 400s
smtp_tls_note_starttls_offer = yes
smtp_use_tls = yes
smtpd_banner = $myhostname ESMTP $mail_name
smtpd_delay_reject = yes
smtpd_error_sleep_time = 15
smtpd_hard_error_limit = 10
smtpd_helo_required = yes
smtpd_helo_restrictions = permit_mynetworks, reject_unknown_hostname, reject_invalid_hostname, reject_non_fqdn_hostname, regexp:/etc/postfix/helo.regexp, permit
smtpd_recipient_restrictions = permit_sasl_authenticated,permit_mynetworks,reject_unauth_destination
smtpd_reject_unlisted_recipient = yes
smtpd_sasl_auth_enable = yes
smtpd_sasl_security_options = noanonymous
smtpd_soft_error_limit = 5
smtpd_timeout = 480s
smtpd_tls_auth_only = no
smtpd_tls_loglevel = 1
smtpd_tls_received_header = yes
smtpd_tls_session_cache_timeout = 3600s
smtpd_use_tls = yes
strict_rfc821_envelopes = yes
tls_random_source = dev:/dev/urandom
transport_retry_time = 240
unknown_address_reject_code = 450
unknown_client_reject_code = 450
unknown_hostname_reject_code = 501
unknown_local_recipient_reject_code = 550

Remove the reject_unknown_hostname and restart postfix.

////

Man - that seems to have fixed the issue. Mail has successfully passed through. Am I in any danger for removing the line in regards to being spoofed or SPAM'd to death?

A little. But you have to balance that with your desire to receive legit mail. Me, I do not have that directive enabled in my postfix.