This issue isn't related with Autodiscover, in a coexist lab, you just need to one autodiscover record. About the connection issue, it is related with the virtual directories configuration on your Exchange server. About the certificate issue, it is related with the service URL and the subject that contained in your certificate.
Could you provided detail information about the certificate error? It will help us to narrow down this issue.
I also suggest you provide those information below to us:
Get-OutlookAnywhere | Select Server,InternalHostName,ExternalHostName
Get-MAPIVirtualDirectory | Select Server,InternalURL,ExternalURL
Get-OABVirtualDirectory | Select Server,InternalURL,ExternalURL
Get-WebServicesVirtualDirectory | Select Server,InternalURL,ExternalURL
Get-ClientAccessServer | Select Name,AutoDiscoverServiceInternalUri
Get-OWAVirtualDirectory | Select Server,InternalURL,ExternalURL
Get-ECPVirtualDirectory | Select Server,InternalURL,ExternalURL
Get-ActiveSyncVirtualDirectory | Select Server,InternalURL,ExternalURL
Get-PowerShellVirtualDirectory | Select Server,InternalURL,ExternalURL
Get-ExchangeCertificate | fl Subject,CertificateDomains,Services
I would also suggest you create a new mailbox on this new Exchange server, then check the look up step from Outlook "Test Email Autoconfiguration", those information will help us to know the detailed information in your organization and help you to narrow down it.
Remember remove privacy information before posting result on this forum.
This tool also useful to you: Exchange Deployment Assistant
If the response is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.