MX or A record issues

MX records are fin but the domain has no dns record at all. Is that a possible error? What dns record the client should add?

Yes, some mail servers, upon receipt of an email, check to see that the domain for the sending user, not just the sending server, has DNS records. I think it's a bit silly, and not a great check for spam, but it is what it is. Your client most likely needs to simply put an A record in for their ourclientcompanyname.com apex domain. Get them a $5 hosting account and a single page informational website for good measure, just to be nice.

EDIT:

Buried within ye olden RFC 5321, it says in section 2.3.5:

Only resolvable, fully-qualified domain names (FQDNs) are permitted when domain names are used in SMTP.

Noice! I still think it's a silly to think of it as a spam deterrent and is a correlation/causation conflation, but hey at least it's a documented standard and following it has some positive side effects on the spam folder! Who has two thumbs and just got RFC schooled?

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

In order for mail to function properly there are three DNS records that are required.

1. A Record - Host name to IP address mapping

2. MX Record - The MX record is bound to the A Record for the mail server

3. Reverse Lookup - The IP address needs to be bound to the A record for reverse lookup (SPAM Prevention)

As well, the PAT address at the firewall needs to be set for the mail server so the public IP (source IP) of the mail server matches the reverse lookup.

You will typically need to get with your ISP and have them create the reverse lookup if they own the IP addresses you are using on the public side.

Note: There is no RFC regarding Forward-Confirmed Reverse DNS. It is simply a best practice.