MS has been porting the Live/Outlook cloud services from AWS to their Office 365 platform on their Azure servers, and they're importing its users in large batches - the last of my accounts were ported over the weekend and I got the same "error" you did. The fix was to delete and add the same account from the Internet Accounts Preference Pane (I also deleted the Keychain for that MS account).
I re-added the account as an Exchange account; it was set up as an Exchange account as well. The new account settings in Keychain are entirely different than they were just a few days ago. The account is working fine now - mail, calendar, notes, but the contacts are still having their "issues" with an Exchange account as its been for years now...
FWIW, I was having issues with my Win 10 Mail app as well - a bit more tricky to "fix" as that account is also my user, and I had to remove that account and set it up again (a bit of a PITA - thanks, MS...
).