Could you, please, clarify how many instances of Adaxes service you have? Do they share common configuration?
The error occurs because the credentials used to access Exchange on-premise cannot be validated by Exchange Online. To remedy the issue, try to specify the credentials for the domain explicitly. Credentials do not replicate between the services sharing common configuration, the domain logon credentials should be specified explicitly for each service in the set. For information on how to change the credentials, have a look at the following help article: https://www.adaxes.com/help/?HowDoI.Man ... nInfo.html. On step 5 of the guide, select This account and enter the credentials of an account with Organization Management and Recipient Management roles assigned in Exchange on-premise.
You can use the credentials of the Adaxes service account, just make sure that you specify them explicitly rather than selecting the Adaxes service account option.