Had the same issue. Here’s what I did to troubleshoot.
See where it fails by running (change email@example.com to your destination)
exim -bt firstname.lastname@example.org
Check if your hosts are getting resolved properly by running these commands on the terminal.
# the following should show the short 'hostname'
# following should show the full domain name (without www or subdomains)
# following should show the external IP (not 127.0.0.1)
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)
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 :\
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.