Maybe this coule be helpful
docs.microsoft.com/.../admin-how-setup-email
In case it won't give you any hint or risolve the problem, please be in touch with your CSP/Reseller partner and have them troubleshoot it. If they cannot make it to resolve the problem, they could think of reaching out to support to receive some hint on this with a more detailed scenario explanation and logs.
Keep in mind that Microsoft currently supports (as of today)
NAV 2018
BC 14.x, 18.x, 19.x, 20.x