What is the first thing you should do if your identity is stolen?

  My Internet Identity was stolen in early June. 

This is my advice to those whose identity might have been stolen. 

The first thing to do is not to change your passwords etc. Immediately log into your account and note down any suspicious transaction, especially where money or resources are involved. Make sure your login access to the institution is easy and that you have alternate ways of getting verified. In my case, this was a circular reference and there was no way out of the loop. Only after making sure, you can access all accounts for which you have turned on two-factor verification (two-factor verification turned off), you should take other measures such as changing passwords, reporting to credit agencies, FBI, etc.

If you do not heed the above you will be facing hours of useless telephone calls, emails, mail, etc.

T-Mobile, my communication provider, strongly recommended that I should change the telephone number as the phone(s) were compromised. I immediately changed my phone number which landed me in this two-factor hell.

Although at the back of my mind, I had the feeling that I may face other problems while updating it at other contact addresses, I opted to change immediately. Ever since that date, my Office 365 has not allowed me to log in. It allows me to change provided my "Old phone numbers" can receive text messages or phone calls. This is impossible as the phone(s) have changed. There is no other option in the two-factor authentication which was never modified. 

This also created a problem with my back accounts which had two-factor authentication with only a phone for verification. Bank of America was the worst. It left me with no means to correct this issue. Finally, I had to write to them twice as the first one addressed to the bank branch manager did not respond despite my writing to him being delivered by the next morning mail. I am waiting for the other mail from BOA.

Microsoft HELP/ Support is useless as it does not address this issue. A simple recipe according to Microsoft is to log in to the app and update your telephone number. Little does it care whether a client can log in with two-factor authentication where the phone might have changed. Phone support (1-800-642-7676) is also useless as it advises you to try logging in again. There is no "human" support.

This is displayed while logging in. There is but one option, but it refers to phones that are changed. There is more information on an Akamai site which is useless.

I have tried numerous ways to find some sort of support from Microsoft and I have been unsuccessful. 

I am planning to get some help from the Microsoft Community and will have to wait it out. The company gets big, and help gets reduced as it does not care about a few pissed-off users.