EVERYONE WHO DOESN'T KNOW THEIR MSA, OR DOESN'T RECOGINIZE IT PLEASE READ:
Have you ever taken advantage of the 3 free trials for a brand new xbox?
Have a sibling who used your email, had a friend who created your account, or other circumstance of the like?
IT'S INCREDIBLY POSSIBLE, AND VERY LIKELY THAT YOUR MSA IS NOT YOUR CURRENT OR BEST EMAIL OR WORST CASE, IT WAS MISSPELT.
If you are signed into xbox.com and your seeing a weird gamertag or having to accept TOU and "Joining Now" that is not your current MSA for your good gamertag.
SO, you need to figure out what your MSA is.
Thankfully for most with the new TFA on the console when it asks for your email & password your email is auto-populated. If you are seeing a mis-spelt email, the "wrong" email, a parent's email, it doesn't matter what you think, that's what Microsoft has on file for that gamertag.
Unfortunately after a few rounds of getting it wrong it won't auto-populate. Either way you need to reset that email's password on account.live.com.
If it was misspelt, say gail.com, gamil.com instead of gmail.com, ect when you go to account.live.com you sign in with that incorrect spelling as the Microsoft Account. TRUST ME.
-As far as resetting the password, most likely it's going to send an email reset link to that non-existent email so hopefully you have a security question or another valid proof on your account.
If your gamertag was created as a secondary to a family pack and the primary didn't put in an email because you didn't have one, you didn't want to give you one, etc and it gave you firstname.lastname@example.org, that is your MSA and you need to use that as the MSA and reset that.
-Luckily for most in that instance, the primary's email is the proof you receive the email reset link.
Very rare instances are your account being compromised and they changed your MSA, but they would have had to have had your gamertag on their console for more than 30 days to do so.
-In that case you can call support, but if they don't find Unauthorized Access your still having the same issue only longer without your account.
Some of the older live accounts may have the advantage to re-create the email attached to their MSA because the email is so old it was dropped by domain and you can re-create it.
I hope this helps. It's irritating I know, but seriously your MSA is your responsibility, always has been. MS will never have your passwords and you need to add proofs to keep from losing your account because in the future you won't have any options for resetting your password. That's all TFA is doing, making you add options to reset your password for the future. In regards to the other network its actually kind of scary how easy they give out resets, imagine a pissed off "friend" ex-girlfriend, brother, neighbor, all they need to know is basic info and the last 4 of your cc, which they can get from a receipt or something.
IF you can at least provide ownership, which I think those with a current subscription generally can, they can tell you what your email is, and then you have to reset it. If you have done the ASCR form that you've been instructed to do before several times, and still have the rejection emails you can call support and they can escalate to prove ownership with the recovery request numbers from those rejections, and your console ID#.