I'm a normal everyday Xbox Live account user and because I had so much stress not being able to use my Xbox Live, I decided to help others out with the super crappy problem.
One day, trying to log onto my Xbox profile, it asked me for my email, password and remember password. "WHY!? I dont bother my account so why is there something wrong?" I tried all the ideas: Adding more proofs like phone # and alternate email and still nothing. Then I tried deleting and redownloading my account on Xbox, then I couldnt even download it or get onto any other account on my Xbox. So I finally called customer support and after an hour or more on the phone I got it fixed almost immediately. Here's how:
1. Go to Windows.Microsoft.com and sign in.
2. Scroll to the bottom and click Hotmail under Products.
3. Scroll to the center to click Get Help With Hotmail.
4. Click the third link, My Hotmail is Temporarily Blocked.
5. In front center click Contact Support.
6. Click the first link *Your account has been temporarily blocked.*
7. Fill out the short form with descriptions to your best and submit.
8. Last but not least, some OKs and confirmations I believe.
9. You can immediately try downloading ur profile and connecting to Live again on your Xbox.
*It may not work immediately for everyone like it did for me, but all u have to do is wait and try again whenever u want.*
I hope this helps,