I've been running into this a lot lately where an old certificate can't be removed from Exchange as it is bound to a send connector and most commonly it's on a hybrid-mode Exchange configuration.
Here's how to get rid of it easily on Exchange and then delete the old certificate.
First, run the command to get the certificates on the Exchange server.:
Get-ExchangeCertificate | fl
This will return a full list of all certificates on the server. Make a note of the Thumbprint of the certificate you want to keep. That's the only one needed.
Now, shut off the "Microsoft Exchange Transport" service using Exchange PowerShell:
net stop "Microsoft Exchange Transport" or Stop-Service -Name MSExchangeTransport whichever you prefer.
Next is to get the name of your Send Connector shown in the error when trying to remove the certificate. You'll need that name in the next command to remove any certificates that are bound to the connector:
Set-SendConnector -Identity "Outbound to Office 365 - 5c10806d-35cb-6645-8b8f-fde431830769" -TlsCertificateName $Null
At this point you can now delete the old certificate(s) as they're no longer bound to the connector.
Now run these two commands to set the variables for the certificate you want to keep. This is where having the Thumbprint for the new certificate is needed.
$cert = Get-ExchangeCertificate -Thumbprint 6B6CB53DF162724D4F3AD97E508C5BBF072DCE8
$tlscertificatename = "<i>$($cert.Issuer)<s>$($cert.Subject)"
Do not change the syntax on the 2nd command. That's used to pickup that variable for the final command.
Use this command finally to assign the new certificate only to the Send Connector:
Set-SendConnector -Identity "Outbound to Office 365 - 5c10806d-35cb-6645-8b8f-fde431830769" -TlsCertificateName $tlscertificatename
Finally, restart the Microsoft Exchange Transport service and you're finished.
net start "Microsoft Exchange Transport" or Start-Service -Name MSExchangeTransport
This completes the removal of any old certificates bound to the Send Connector so you can delete them from the server. As a precaution, always test your mail flow service to make sure everything is working properly.
Good luck!
