Seems like you might have blocked Basic auth based on your experience, which is recommended. But without more details on your setup in both Exchange and Azure AD it is hard to assist you. I would start looking in the Azure AD Signin logs to see what happens when you try.
I would also double check that Exchange Online supports Modern Auth.
Get-OrganizationConfig | Format-Table Name,OAuth* -Auto