I had a very similar problem with Skype (also now a Microsoft company).

I had been using this Skype account for years. Suddenly one day out of the blue my account was suspended and I was asked to recover it, no biggy I thought, since I had access to the email account AND didn't set it up with gibberish (i.e. real name, real address, etc).

Here is what Skype asked for (with remarks):

      - Contact email (easy)    
      - Account Creation year (who knows this?!)    
      - Country of registration (easy)    
      - Payment history (huge problem, discussed below)    
      - Skype 3 contacts (buggy, needs the Skype usernames, not "friendly" names)   

On the face of it this seems "easy." Except it is super buggy/finicky and Skype's support has zero alternatives. In fact they told me to register a new Skype account if I couldn't complete the form(!). They even sent that reply to my registered email address.

The main issue I had with the above form was, Account Creation Year (I didn't know it!), Skype contacts (it needs either Skype name (e.g. BSmith123) or email address, NOT profile names/friendly names e.g. "Bob Smith").

Payment history is just horrifyingly terrible. I tried my current credit card (nope), current debit card (nope), old debit card (nope), and even somehow tracked down my long since cancelled old credit card (nope). I also tried other with a comment (nope).

After being without access to my Skype account for several weeks, I tried setting my Payment History to "Never paid for Skype" even though I actually had (many many times)! Worked. After logging in I had an expired credit card on the account (one of the ones I tried several times).

In order to finally gain access to an account I lost access to for reasons I still don't understand, I had to:

      - Search through several boxes looking for old cards    
      - Pull down a backup of my Skype profile and extract Skype profile names for my contacts using an SQLite tool     
      - Search tons of historic emails for my creation date (never did find it)   
      - Contact support half a dozen times (they were utterly unhelpful).