Могу предложить только следующее:
перезапустите браузер, перейдите на https://account.live.com/proofs
введите данные для входа в Ваш Live ID аккаунт
попробуйте изменять контрольные сведения там, например, поставить телефон в России и емейл, а контрольный вопрос удалить или создать заново и т.п. Не забудьте записать новые значения.
В доверенных компьютерах может быть несуществующая машина, тоже её удалите, а Ваш сделайте доверенным.