Recently we moved exchange certificates to a certificate with no local SAN’s inside to be in compliance . This involves creating and A record for your external domain name internally , then changing all internet and external paths to the full qualified external domain name. Digicert has a great guide to do this : https://www.digicert.com/ssl-support/redirect-internal-exchange-san-names.htm

After this is done, you can reissue the certificate with the local SAN’s removed using a new CSR ( .req file ) generated from Exchange and apply to all client access servers. 

This was done , however a few ( not all )  users in our organisation where getting the prompt above linking to autodiscover.domain.local . Checking on the effected users , it seems their Outlook were referencing old Exchange accounts that didn’t exist anymore in exchange. Removing these old accounts from outlook and restarting fixed this. Reprofiling will also fix this!