Exchange Online stopped accepting an ordinary username and password over IMAP. That is basic authentication, the legacy kind. The refusal arrives at login and reads like a wrong password, even though the password is right.
App passwords of the Google or Apple kind generally do not exist in Microsoft 365: the default security policy does not issue them. So the usual advice to create one simply cannot be followed here.
What replaces it is OAuth 2.0, where the client receives an access token instead of a password. Over IMAP that token is carried by the XOAUTH2 extension.