Hey there! Nice to meet you!
Based on your description, the hacker was able to remove the account's primary email address/security info and replace it with their own email address, which is why you received an error that your account has not been found.
The only way to recover a hacked account is through the official Microsoft troubleshooter guide:
If the account recovery web form doesn't work, and since the security info has been replaced by the hacker, I'm afraid there is no other working method to recover the Microsoft/Minecraft account, and Microsoft Support cannot help either.
Thank you for your understanding.
Best regards,
Darhyl