Exim4: all relevant MX records point to non-existent hosts

Solution 1:

The DNS server of the recipient domain isn't configured properly. You can find more information about the problem on the Exim wiki.

Edit: Now when I have the recipient domain, here's some updated information. The MX servers for the domain are:

$ dig +short mx dresssmall.com
8 smtp.dresssmall.com.
9 pop.dresssmall.com.
10 mail.dresssmall.com.
7 pop3.dresssmall.com.

The problem is that they don't have proper A records:

$ dig pop3.dresssmall.com | grep NXDOMAIN
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 60414

Above I pasted only the MX with lowest priority for brevity, but all of them doesn't have A records.