I was able to resolve this issue, I had inadvertently set the hostname to the domain name. Setting the hostname to:

something.domain.com and then reconfiguring exim fixed the issue.

Had the same issue. Here’s what I did to troubleshoot.

See where it fails by running (change example@domain.com to your destination)

exim -bt example@domain.com

Check if your hosts are getting resolved properly by running these commands on the terminal.

# the following should show the short 'hostname'
hostname

# following should show the full domain name (without www or subdomains)
hostname --fqdn

# following should show the external IP (not 127.0.0.1)
hostname -i

If all is good, and if the block is still unroutable, force the exim configuration to route it. So edit /etc/exim/exim4.conf.template file, and find the block within .ifdef DCconfig_internet. Add this as the first rule. (Change example.com to your domain)

my_domain_routing:
  debug_print = "R: dnslookup for $local_part@$domain"
  driver = dnslookup
  domains = example.com
  transport = remote_smtp
  # ignore private rfc1918 and APIPA addresses
  ignore_target_hosts = 0.0.0.0 : 127.0.0.0/8 : 192.168.0.0/16 :\
                        172.16.0.0/12 : 10.0.0.0/8 : 169.254.0.0/16 :\
                        255.255.255.255
  no_more

Run the routing test again to see if it passes now.

Note about exim4.conf.template file. This can get regenerated if you run the config utility again. To avoid this, duplicate this change in the /etc/exim/conf.d/routing/ folder as well.