Столкнулся недавно с такой же проблемой, потерял доступ к аутентификатору после его обновления, был подвязан номер телефона, по которому было возможно восстановление. Но видимо в связи с их политикой в отношении России, этот способ более не доступен, а других нет. Еще у них есть способ восстановления аккаунта через подтверждение всевозможных данных других аккаунтов по типу скайпа, иксбокс, хотмэйл, старых паролей, но если ничего этого нет или данных мало - до свидания...