内容に勘違いがあったので公開後内容を一部修正しています。
結論から言うとProject内のプレハブではなく、プレハブから生成したHierarchyに配置済みのオブジェクトをインスペクターに登録してしまっていたのが原因でした。

初歩的なことだと思うけど、Unityでちょっとハマったのでメモ。

Prefab化している特定のtagが付いたゲームオブジェクトをFindGameObjectsWithTagで全検索した上でDestroy（全削除）したところ、その後インスペクターから登録していたPrefabを使用して再度Instantiateしようとするとエラー（Missing）になってしまった。

（以下のPrefab「Stage001」「Stage002」「Stage003」を画面上から一度全破棄した上で再度生成しようとした）

MissingReferenceException: The object of type ‘GameObject’ has been destroyed but you are still trying to access it.
Your script should either check if it is null or you should not destroy the object.

ちなみに削除は以下の様な感じで行っていた。

// Stageタグを持つオブジェクトを全て破棄
GameObject[] stages = GameObject.FindGameObjectsWithTag("Stage");
foreach (GameObject stage in stages)
{
  Destroy(stage);
}

原因（訂正追記あり）

FindGameObjectsWithTagの仕様の勘違い。

FindGameObjectsWithTagはシーン内に配置されているオブジェクトだけじゃなく、インスペクターから登録しているオブジェクト（Prefab）も検索対象になる。

つまりインスペクター上から登録していたPrefabも削除してしまっていたため、Instantiateの際に生成元のPrefabが見つからないエラーが生じていた。

そうなのね。。知らなかった。。

【訂正】
上記間違ってました。正しくはPrefabを元にヒエラルキーに登録したゲームオブジェクトをインスペクターに登録してしまっていたため削除したゲームオブジェクトをFindしてMissingになっている、でした。

対策（訂正追記あり）

ということで、インスペクターから登録しているオブジェクトと画面上に生成したオブジェクトを区別できれば良い。

色々方法があると思うけど、例えばそのPrefabにアタッチしているスクリプトに判別用のbool型の変数（例：bool onScene等）をデフォルト値Falseで用意、で画面上に生成する際はonSceneをTrueにする。

その上でFindGameObjectsWithTagの後for文で処理する際にif文でonSceneの値で条件分岐させる等すればOK。

ざっくり以下の様な感じ（StageManagerはPrefabにアタッチされているスクリプト）。

もう少しスマートな方法がありそうだけど、とりあえずこれで解決できる。

// Stageタグを持つオブジェクトを全て破棄
GameObject[] stages = GameObject.FindGameObjectsWithTag("Stage");
foreach (GameObject stage in stages)
{
  if (stage.GetComponent<StageManager>().onScene == True)
  {
    // 画面内に出現しているステージのみ削除
    Destroy(stage);
  }
}

【訂正】上記間違ってました。原因のところでも訂正したようにPrefabからヒエラルキーに登録したゲームオブジェクトをインスペクターに登録していたことが問題なので、大元の（Hierarkeyに配置したものではなくProject内の）Prefabをインスペクターに登録すればOKでした。