Do you have other partner applications that have the certificate imported? You may have to remove the partner application and re-configure it.
Get-PartnerApplication
Remove-PartnerApplication <application name>
.\Configure-EnterprisePartnerApplication.ps1 -AuthMetadataUrl '<url>' -ApplicationType <type>
Here are similar issues for your reference:
Exchange 2016 / Skype for Business - MSExchange OAuth Error,
Exchange 2013 Partner Applications and Error 2008.
Please Note: Since the web site is not hosted by Microsoft, the link may change without notice. Microsoft does not guarantee the accuracy of this information.
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.