Security certificate cannot be verified

Hello,

I’ve configured a let’s Encrypt cert, got the green ok message and upon configuring Outlook, a “Security certificate cannot be verified” message appears: https://www.screencast.com/t/SDIK7m50xvu

The cert is apparently renewing correctly (Automated certificate renewal for domain.com has succeeded 2021-11-25 01:21)
DNS config for the domain is resolving directly to safari.mxroute.net
Client clicks on Yes every time they start Outlook, and it continues coming back. It’s really bugging to them.
Anything I’m doing wrong?
Thanks

So, just for clarifying, you’ve made a CNAME for mail.mydomain.com pointing to safari.mxrouting.net and DA creates LE certificate for that without issue? (The root mydomain.com is irrelevant in this case.)

Are the Outlook and Windows version new/current, or older versions?
(Older versions will have issues with the root CA of current Lets Encrypt certs.)