Yes, I saw, and as it's almost always the case, it's a useless response given like a robot. "I'm and advisor".
Here's a possible workaround/solution. Beware: I couldn't find a way to solve Outlook/Microsoft contacts issue. You will still have 10 thousand contacts there, but this solution is for the phone. Here in my country we use WhatsApp, so it wasn't just the phone book being messed up, my WhatsApp contacts list also had 8 thousand (and counting) contacts lol.
HOW TO RECOVER YOUR CONTACTS:
This is assuming you save your contacts (On the Android Phone) on your Google account. FIRST you could try REMOVING from Sync the "Microsoft Exchange Account" and leave only the Google one. I didn't do this first step, because I saw that ME account was also used in other apps or services (My phone is Galaxy A22), so I didn't want to deal with an aftermath of de-sync on other parts of the phone. Here's what I did to get back to normal.
- Go to "Link to Windows" app on the phone, and within the app: Turn OFF "Allow to sync contacts" option. Then, REMOVE the PC device you are linked to (tap 3 dots, select remove). And then, tap "Sign out and unlink".
- Go to the app on the computer, click on your device image (top left), and then when devices appear, 3 dots and remove device to reset that app (this shouldn't be needed as it's unlinked already, but I did it anyways to reset everything just in case).
- Go to your "contacts" app on the phone, and delete all the contacts. I tried this thinking it would only remove the ME account ones (the thousands) and leave the Google ones alone. But no, it deletes ALL the contacts sadly. However, contacts are SAVED IN TRASH FOR 30 DAYS both on Google and Outlook. So, remove all the contacts and restart the phone.
- After phone restart, go to Google.com, top right on "more apps" and go to "Contacts". Here scroll down the menu to "Trash". Here you can select all the Google contacts you had that were also erased with the rest (There SHOULDN'T BE 10 thousand contacts here), so you should be able to select all without issues instead of one by one. Then click "Recover". This will recover the contacts to your Google account. After a little while (but hopefully immediately) the phone should re-sync to the Google account contacts and all your contacts should be there again as they were before.
I hope this helped. One last thing: If you can go here and upvote and also click "Similar feedback" to get a bit of traction on this, so MSFT team can get on this asap. I filed a feedback with high severity post: https://aka.ms/AAk7kvp
Hopefully you can enter even if being from another region. This bug is critical, as someone mentioned above, and it even messes your entire phone/apps. If you need to work with that, having that issue could be a massive problem, especially for people without the time or knowledge to deal with this.
PS: Do not link your phone again, just in case. And as I mentioned, sadly for now, our Outlook accounts will still have 10 thousand+ contacts. I cared only to solve the phone stuff yesterday.