Make sure all of the following are met.
External message delivery health test required permissions for test credentials.
Member of the Organization Management group or the Exchange View-Only Administrators group
Member of the Local Administrators group on each Exchange server
Full access permissions to each test mailbox
All extended rights permission to each test mailbox in Active Directory
For granting “All extended rights permission to each test mailbox in Active Directory”:
1. On Active Directory Users and Computers, select the test mailbox object to open its properties.
2. On the Security tab, click “Advanced” to open the Advanced Security Settings dialog.
3. On the Permissions tab, add the test credentials (i.e., the service account in your case) and select the “All extended rights” for it.
Make sure that the Certificates on your Exchange 2013 Client Access Servers are installed on the Spotlight on Messaging-Unified Communications Command Suite server.
Note: If you're using a Hardware Load balancer with your CAS servers the Internal Message/Mailbox Delivery Health test may always fail with the error in the Problem description, you will need to run the Exchange Modern Delivery Health Test in version 8.3 or later.