Same here. Over 20k contacts. Contacted Outlook Android app support who eventually told me it's nothing to do with them and I had to contact Outlook.com support. Contacted Outlook.com support who told me I needed to contact Outlook.com support...
Since the issue I have deleted the link to windows app on both phone and PC. Deleted all contacts from my MS account in the Google Contacts App. This deletion has carried over to my main Outlook however they remain in Outlook.com and the new Outlook (pre) app on PC.
I've complained to the support and feedback that this issue could be easily resolved if we could just delete our own contacts and not be restricted to 10 at a time. I've had the unfortunate experience that these contacts didn't flow to my Outlook where other seem to have been able to bulk delete.