Hi everyone,
First of all thanks to everyone that tried to help me sort out my exchange. I have now resolved the issue and will add below what i did to resolve it in the hopes it helps someone else some day that may stumble upon this!
The issue was as said in some replies above a problem with my DNS. In my case i did not have a zone for autodiscover.mydomain.com or remote.mydomain.com. All i have to do is create a new zone in the forward lookup zone pointing to internal email servers IP address. After this i then set my auto discover settings and OWA hostname for each virtual directory using the exchanage management console (this can be done in ECP as shown above but i just followed the guide below exactly) . All details of how to sort your dns AND all other autodiscover settings can be found here: https://www.ajtek.ca/guides/exchange-autodiscover-a-guide-to-making-exchange-work-properly/
Make sure you follow the tests for your new dns settings also (in guide).
FOLLOW THE GUIDE EXACTLY SKIP NOTHING. DO an IISRESET after and run below in powershell as an admin to restart exchange services:
Get-Service *Exchange* | Where {$_.DisplayName -NotLike "*Hyper-V*"} | Restart-Service -Force
After this you'll likely still find you have the certificate error..... which is the original question on this thread. You cannot solve this error if you have not set up dns and autodiscover correctly as this is the cause.
Ti get rid of the error simply go onto the client machine, close outlook and go to control panel then to mail. Click show profiles then click add. Give it a name and then click ok, then close the following pop up. It will ask if you want to save the profile without an email account..... click ok. Then change the always use this profile dropdown box to the new profile. Click apply then okay and close the window.
Now when you launch outlook it will be like first time launch, connect to the email account, choose outlook.com and you are done! No more cert errors.