Почему двухфакторная аутентификация не ухудшает безопасность?
То есть, зная пароль, но лишившись номера телефона, должно быть можно восстановить номер. А имея номер телефона, должно быть можно восстановить пароль.

Но в чем тогда выгода? 
В том, что вы привели пример НЕПРАВИЛЬНОЙ настройки двухфакторной авторизации.
Восстановление доступа должно идти через службу безопасности, возможно даже с личным присутствием.
А то, как двухфакторная авторизация сделана в общих мобильных сервисах - это так, для галочки и небольшого усложнения.
Как правило для сброса номера телефона как минимум требуется пообщаться с техподдержкой и убедить её, что ты - это ты, а не дядя вася мамкин хацкер. Ну а с телефоном всё проще - как правило они у пользователей под каким-никаким, а паролем, да и вирусню на телефон не так уж и просто закинуть.