RFC 5321 section 2.3.5 requires that domain names used in email be resolvable to addresses.
From the relevant parts:
Only resolvable, fully-qualified domain names (FQDNs) are permitted
when domain names are used in SMTP. In other words, names that can
be resolved to MX RRs or address (i.e., A or AAAA) RRs (as discussed
in Section 5) are permitted, as are CNAME RRs whose targets can be
resolved, in turn, to MX or address RRs. Local nicknames or
unqualified names MUST NOT be used. There are two exceptions to the
rule requiring FQDNs:
- The domain name given in the EHLO command MUST be either a primary
host name (a domain name that resolves to an address RR) or, if
the host has no name, an address literal, as described in
Section 4.1.3 and discussed further in the EHLO discussion of
Section 4.1.4.
This is not a new requirement; RFC 2821 section 2.3.5 (2001) had similar language.
The domain name, as described in this document and in [22], is the
entire, fully-qualified name (often referred to as an "FQDN"). A
domain name that is not in FQDN form is no more than a local alias.
Local aliases MUST NOT appear in any SMTP transaction.
If your mail server says EHLO company.example
and company.example can't be resolved to an address, then it's perfectly valid to reject that connection. The same is true of the domain names used in the sender and recipient addresses (with the exception of postmaster, which doesn't require a domain name at all).
(Prior to RFC 2821, the governing standards were RFC 821 and RFC 974, which date to the 1980s and had to accommodate many non-Internet networks which no longer exist, thus the standards were much less restrictive.)