I'm not sure but we change the password on our mail account in m365 on a recurring basis (because security policy dictates it even though im the only one that knows the password), and I haven't had this problem. I wonder if this is a password complexity thing... Try a simpler password at both ends?
This might help: https://www.faqforge.com/o365/office-365-password-policy/
Allowed Characters
Following are the allowed characters in Office 365 user password:
a - z
A - Z
0 - 9
@ # $ % ^ & * – _ + = [ ] { } | \ : ‘ , . ? / ` ~ “ < > ( ) ;
Disallowed Characters
Following are disallowed characters in Office 365 user password:
Unicode characters like !, ¥, Ą, Ə, ɖ, o̕, Љ, Ԁ, Ա, ؟, ܀, ހ, ߄ etc
spaces
Office 365 User Password
Office 365 password must contain minimum 8 characters and maximum 16 characters and cannot contain a user name. It requires 3 out of 4 the following:
Lowercase characters
Uppercase characters
Numbers (0 - 9)
Symbols like @ # $ % ^ & * – _ + = [ ] { } | \ : ‘ , . ? / ` ~ “ < > ( ) ;
