EWS with Oauth 2 - "SoapFault exception: An internal server error occurred. The operation failed."

We have a working PHP app using Basic Authentication and we migrated to Oauth 2 but we receive this error from EWS.

Uncaught SoapFault exception: [a:ErrorInternalServerError] An internal server error occurred. The operation failed.

Our app was implemented long time ago in PHP using https://github.com/jamesiarmes/php-ews library, but since Microsoft decided to disable Basic Authentication we planned to migrate to Oauth 2. and we updated the library to this https://github.com/facilioo/php-ews which supports the Modern Authentication.  
Also we generated the token using this api https://login.microsoftonline.com/{{tenant_id}}/oauth2/token and client_credentials flow since there is no user interaction.

We use Office 365 Exchange Online permissions with full_access_as_app and https://outlook.office365.com/.default scope to generate the token. We use X-AnchorMailbox header and impersonate soap header as well.

Do you have any clue why we are getting this error and how to fix it?