個人用 Outlook.com アカウントの設定、セキュリティ、プライバシーの管理
質問文の本文を読むと「セキュリティ情報の変更を保留中」ではなく、まだセキュリティ情報の変更手続きをまだしていないように読めます。
また、「アカウントのメアド」というのが、マイクロソフトアカウントのアカウント名(アカウントの i.d.)としての「メールアドレス」のことなのか、セキュリティ情報(本人確認連絡先)のことなのか区別が付きません。一応両方使えなくなっているとして。
まずセキュリティ情報を変更し、それによってセキュリティコードを送れるようにしてから、マイクロソフトアカウントのメールアドレス(主アドレス)を変更する方法の URL を示します。(セキュリティ情報の方は急に新しい新しいメールアドレスを入れても送られません)
セキュリティ情報(連絡先)の追加から、現在それが無効になっているようですから「すべての情報が不明」として入り、新しい連絡先を入力して、30日待つ必要があります。
その上で、マイクロソフトアカウントのエイリアスを追加し、メールアドレスとしては無効になっている現行プライマリーを、追加したセカンダリーと入れ替える手順になります。
Microsoftアカウントにセキュリティ情報を追加する方法
https://support.microsoft.com/ja-jp/help/4026473/microsoft-account-how-to-add-security-info
Microsoft アカウントのメール アドレスまたは電話番号を変更する
https://support.microsoft.com/ja-jp/help/12407/microsoft-account-change-email-phone-number