これは、あなたのメールアドレスがどこかから漏洩し、公開状態になっていることが原因だと思われます。私も同様の経験があり、最終的に以下の方法で解決しました。それは、サインインに使うメールアドレス（エイリアス）を変更することです。
手順:
Microsoftアカウントのページにアクセスし、「あなたの情報」をクリックします。「アカウント情報」セクションにある「サインイン設定」または「サインイン設定の変更」を選択します。「アカウント エイリアス」のセクションで、誰も知らない新しいメールアドレス（または電話番号）を「エイリアスとして追加」します。注意: ここで元のメールアドレスを削除しないでください。完全に削除されてしまいます。追加した新しいエイリアスを「プライマリにする」に設定します。ページ下部にある「サインイン設定を変更する」をクリックし、サインイン許可のチェックを、元のメールアドレスから新しいエイリアスのみに変更します。これで、攻撃者があなたの古いメールアドレスでサインインしようとしても、「そのアカウントは存在しません」というメッセージが表示されるようになります。一方、あなたは引き続き古いメールアドレスでメールの送受信が可能です。
補足ですが、セキュリティページの「すべての場所からサインアウトする」を実行すれば、すべてのデバイスから強制的にサインアウトできます。