Hi. I'm Brian and I'll try to help.
The usual cause of this type of compromise is due to using the same password for more than one account or service. If any service or account using that address and password is compromised, they all will be in short order. Every account or service you have should have a long, complex and unique password. You can check whether or not the address or password is part of a data breach is to visit https://haveibeenpwned.com/. This is a device run by a well-known Microsoft MVP and security expert and is perfectly safe.
As much as I hate to say it, once the address of a Microsoft account gets changed, that account can never be recovered and if you have financial information connected to that account (like a credit card), you should immediately contact the financial institution and inform them so you don't get your money stolen.
Since you were using a gmail.com address as your Microsoft username, you can create a new Microsoft account using that same address, but anything associated with the old account, like games you've purchased, is gone for good.