We are unable to send e-mail to certain internet domains.

The mail returns with a message : the domain of sender is not found.

By running the report on dnsreport.com we get the following error.

ERROR: OURDOMAIN.COM has no CNAME entry, but your DNS servers also report
that the entire domain OURDOMAIN.COM doesn't exist! This can cause many
problems, as DNS servers may cache this 'negative response', preventing
people from getting any DNS responses on this domain

Other mail work fine.
http works fine.
It seems that some mail servers are testing the existence of the domain
before accepting mail. (anti spam). Those particular mail servers are
not succeeding in resolving our domain.

I can't figure out what we are missing here, since we have another
similar configured domain on the same DNS server wich works just fine.

Any help would be appreciated.