Unable to move SDP Online Mail to modern authentication (O365)

Asking here because someone might have had this issue and found a solution.

Curently SDP Mail server is setup using POPS with our O365 account. Due to security getting tighter, we have to migrate to Modern authentication (All user accounts are going under MFA and conditionnal access rules)

After choosing Office365 going trough the authentication process of I am greeted with this error (the code is always different everytime I try to authenticate an account)

Error while adding account : com.adventnet.vo.mail.account.MailAccountException: BJX3 BAD User is authenticated but not connected.

I have confirmed that the password was correct

I have tried Upgrading the account licence to the same licence as the users

This account is Sync from an on Prem AD (Hybrid environment)

Looking at the Azure Sign-in logs, I see success connection attempt from SDPOnDemand

Looking at the conditionnal access logs, I see success connection attempt from SDPOnDemand

Note that conditionnal access should not apply to this user because he was not added to the security group. Conditionnal access filters connections outside US and Canada (allows IPv6 due to not being Geo localized).

Anyone has any insight on how I can tackle this issue?

I can provide logs and perform extra tests if required