2ファクタ認証 前のiPhoneを探すしかないのでしょうか？

何か誤解があるように思います。iPhoneをリセットしても2ファクタ認証の解除が求められることはありませんし、如何なる状況でも2ファクタ認証の解除が求められるようなことはありません。2ファクタ認証の解除はそもそもできません。

iPhoneをリセット（初期化）する際にはパスコードと設定されてるApple IDのパスワードが求められるだけです。

同じApple IDで再セットアップする際には信頼できるデバイスに届く確認コードが必要ですけど、信頼できるデバイスにアクセスできないため、確認コードがわからないということかな？

後の祭りではありますが、信頼できる電話番号には複数の電話番号を登録しておくべきです。そうすれば、特定のデバイスにアクセスできなくてどうにもならないという事態を避けることができます。今の場合なら、現在お使いのiPhoneの電話番号を登録しておけば何の問題も起こらないのですが。たとえiPhoneをリセットしても、同じsimで使ってる限り、同じ電話番号でsmsは使えますので問題は起こりません。

これはどうでしょう？

Apple ID のパスワードをリセットできない場合にアカウントの復旧機能を使う方法 - Appleサポート

このサポート記事は信頼できるデバイスにアクセスできない時の対応です。