After researching this further, I found the solution and the cause (although I don’t really understand the cause). So it seems this issue must have started when I moved from Google hosting my domains to Cloudflare hosting my domains. It seems to have something to do with Cloudflare’s Public DNS (which is referenced in the below articles). If someone can explain why moving from Google DNS to Cloudflare DNS broke this, I would greatly appreciate the education.
In summary, some emails were being blocked by Exim4 and Spamhaus and being logged with a misleading error message that the sender’s IP was in a blacklist on Spamhaus, which it wasn’t. I still have no idea why it was being blocked or that was the error message. But here is the fix. This was the post that I stumbled upon which helped me to solve this:
You have to register for a Spamhaus DQS account, which will provide you with a query key that you can then add to your /etc/exim4/dnsbl.conf file. The details of how to register the account and update Hestia are on the HestiaCP documentation pages here (Scroll down to the section titled: Rejected because [ip] is in black list at zen.spamhaus.org. Error open resolver):
This fixed the blocking issue. It’s kind of annoying that the error messages are completely misleading, which made it difficult to identify what was actually going on, but this did take care of the issue.
I’m still wondering if the above account registration was necessary, or could I have simply went with KPV’s solution. I would still like to know how to use KPV’s solution if it’s easier and doesn’t require the DQS registration with Spamhaus.
Other related articles I came across on Hestia’s discord forum to help research this, in case others are interested…