決済モジュールの注文情報確認画面と決済情報入力画面を戻るボタンと次へボタンで行き来するとorder_idがどんどん進んでいく現象も確認しており、決済情報にすら残っていないパターンはこれで進んでしまった物かもしれません。

dtb_order_tempの動きを把握してないので何とも言えませんが、
order_idの欠番、決済情報はあるが受注情報が存在しない物のパターンは以下の通りになっております。（それぞれorder_idをキーにした場合です）
1, dtb_order_tempに存在しない、dtb_orderに存在しない、決済情報が存在する
2, dtb_order_tempに存在する、dtb_orderに存在しない、決済情報が存在する
3, dtb_order_tempに存在しない、dtb_orderに存在しない、決済情報が存在しない

引用：

EC-CUBE の決済モジュールの仕様は, shopping/complete.php の前で呼ばれる shopping/load_payment_module.php の中で処理を完結する必要があります.
上記の処理を行うためには, 決済モジュールの仕様上困難だと思われますので, 独自にカスタマイズした方が良いかもしれません.

shopping/complete.phpをそのまま使用するためにこのようなフローになっているのかなとは思うのですが、
何かこのファイルを使用しなければいけない制約や背景などがあるのでしょうか？

カスタマイズするとしたらshopping/complete.php以外に何もしない完了画面を用意して決済モジュールの処理を変更、
新しく作成した完了画面にリダイレクトが一番の近道かなと思っております。

1, shopping/complete.php中の処理でメールを出す箇所を追加

本番環境は既に稼動中でして直ぐに対応するのは難しいので、
まずはステージング環境にてGC_Utils::gfPrintLog() を仕込んでもう少しテストしてみます。
こちらのテストで再現できればいいのですが・・・。