そもそもの誤解がある話なので、正しい認識で対処してください。
Microsoft アカウントに登録するメールアドレスなどには「エイリアス」と「セキュリティ情報」の2つがあります。
「エイリアス」は Microsoft アカウントにサインインする際の「ユーザー ID」として機能するもので、実際には単なるラベル(名前の文字列)でしかありません。メールアドレスの形式になっていますが、実際にメールアドレスとして機能するかどうかに関わらずユーザー ID としては機能します。
「セキュリティ情報」は、アカウント内の重要な情報(「セキュリティ情報」自体や支払いに関する情報など)にアクセスする際に追加の本人確認を行うための手段で、メールアドレスなどを登録すると、そのアドレスに本人確認のコードが送信されます。そのため「エイリアス」と異なり実際にメールアドレスとして機能している必要があります。
これが原則ですが、以下の動作があるので誤解を生む場合があります。
- Microsoft 提供のドメイン(outlook.com / outlook.jp など)でエイリアスを作成すると、そのエイリアスのメールアドレスが「Outlook.com メール サービス」でメールの送受信に利用できるようになる
- Microsoft 提供のドメイン以外のドメインのメールアドレスをエイリアスにすると、そのメールアドレスが自動的にセキュリティ情報に登録される(そのためセキュリティ情報の登録は明示的には求められない)
質問されている現在の状況は「Microsoft 提供のドメイン以外のドメインのメールアドレスをエイリアスにして、そのメールアドレスが利用できない(メール受信ができない)」ということですから、問題になっているのは「セキュリティ情報」が受け取れないということです。
※実際に「削除した古いメールアドレスでサインインするこはできます。」と書かれているように、このメールアドレスは「エイリアス」としては機能しています。
セキュリティ情報が利用できず本人確認が行えないとエイリアスの変更も行えないため、「新しいメールアドレスに変更する」にはまずセキュリティ情報を利用可能にする必要があります。
セキュリティ情報が利用できず本人確認のコードの受け取りができない場合は、Microsoft アカウントのセキュリティ情報と確認コード の「セキュリティ情報の管理」- 「セキュリティ情報を更新する」に書かれているように [すべての情報が不明] を選択し、画面に表示される指示に従ってセキュリティ情報(コードの送信先)を置き換えます。詳しくは以下を参照してください。
- FMV Q&A - Microsoft アカウントの「ご本人確認のお願い」で入力する連絡先がわからないためコードを受信できません。 - FMVサポート : 富士通パソコン
- NEC LAVIE公式サイト > サービス&サポート > Q&A > Q&A番号 023925 | Windows 11でMicrosoftアカウントの本人確認ができない場合の対処方法
- 確認コードの問題のトラブルシューティング - Microsoft サポート
なお、セキュリティ情報を置き換えた場合は新しいセキュリティ情報が有効になるまで30日かかります。この期間は短縮することができません。