セキュリティの連絡先は、携帯電話の番号だけでしょうか?
迷惑 SMS 防止設定のため、受信できないことがあるようです。そのような設定がされていないか、確認していますか? それ以外だと、下記のような情報もあります。
また、連続して送信を試すと、異常動作としてロックが掛かることもあるようです。仮想マシンで色々試していた時に、自分も受信できなくなったことがあります。ロックや解除の条件は、自分も知りません。
新しい連絡先を登録することも可能ですが、その場合、有効になるまで 30 日間待たされます。回復キーを取得できず、30 日待てないならば、メディアを使用しての PC の初期化しか手が無いかも知れません。その場合、PC 内のユーザーデータは全て失われます。OneDrive に同期していれば、同期しているデータは失われません。普通は D2D(Disc to Disc)での初期化が出来るのですが、暗号化している場合、回復用のデータまで暗号化されていて、D2D の回復が出来ない事が多いようです。