Backup Exec 15 restore to Exchange 2016 mailbox fails as EWS error/credentials error

Hello,

I currently have the following problem:

If I want to restore a mailobject from a full backup of our Exchange 2016 databases it fails with the following error:

Final error: 0xe0000388 - Cannot log on to EWS with the specified credentials. Review the resource credentials for the job, and then run the job again.
Final error category: Resource Errors

So after this I checked the credentials and the DAG host says "Test failed, Test recommended", which is weird because backups work without a problem, which shouldn't be, right?

I then found this article and checked all the steps, which seem to be OK (I even put the account I have configured for the backup in the administrators group on our CAS servers), the only difference being that it is not our default account, but I have tested it with the default too and the result is the same (i.e. the test fails).

I have also checked the EWS login with https://mail.domain.com/EWS/Exchange.asmx and I get the service page, so the login does work.

Does anyone have any idea how to fix this problem?