個人用 Outlook.com アカウントの設定、セキュリティ、プライバシーの管理
他社のメールアドレスで削除操作を正しくしたのであれば、新しいアカウント作成の時に使えるはずです。
削除操作を正しくしたのかどうか、エイリアスの表示の所に確かに表示されていないのを確認のこと。(セキュリティ情報とエイリアスは別もの)
(前コメントの資料参照)(同じアカウントへの再使用は制限があるかもしれません)
あとはたまたま他人が使っていたら使えません。(組織のアカウントも)
正しいアドレスを入れて取得済みと表示されるのであれば、他に対処法はありません。
Aのアドレスでサインインしようとしたら、どう表示されますか。
追記:マイクロソフトアカウントに他社メールアドレスを使いたい場合、まずマイクロソフト発行のメールアドレス(outlook.jp/com, hotmail.com )で作っておいて、それにエイリアスとして他社メールアドレスを追加するのがいいと思います。