Just in case you will bump into the same problem or if I will forget how to solve it…
If you want to use a file with a list of IP addresses that are allowed to relay mail through your server, you need to use net-iplsearch instead of plain lsearch. Plain lsearch will not work and you’ll get all those ‘relay denied’ errors.
hostlist relay_from_hosts = net-iplsearch;/etc/exim/relay_from_hosts
Specify IP addresses (and network masks if you wish) one per line (or with other separators that Exim understands).