Hello,
Since your Microsoft account was compromised and the email address was changed, I recommend starting with Microsoft's Sign-in Helper to determine the appropriate recovery process.
Please go to:
Follow the prompts for your account. If you can no longer sign in, select No when asked whether you can access the account.
Microsoft actually has different account recovery forms, and they are not the same.
1. Account Recovery Form (ACSR)
This form asks detailed questions about your account history, such as previous passwords, email contacts, and email subject lines.
2. Recover My Account
https://aka.ms/recovermyaccount
This is a separate recovery process that may be offered for account takeover situations. It asks for more basic information, such as your name, last password change, and usual device.
==================
Please use the recovery form that Microsoft's Sign-in Helper directs you to, rather than choosing one yourself.
If the account's original email address is no longer recognized, the Sign-in Helper may display "Username not found." The exact message is important in determining the next step.
Unfortunately, community members cannot access account records, manually verify ownership, or override Microsoft's recovery decisions.
=============
Can you tell me what account status the Sign-in Helper displays and which recovery form or option it recommends?
You can share the form's title or public website URL, but please don't share your email addresses, passwords, or verification codes here.
If I know which form you are filling out, I can provide a bit further instructions on how to best use the form, or if there's any limitations.