ios18にしてから履歴検索が上手くできなくなった

MacのSafariでWebブラウズの履歴を検索する - Apple サポート (日本) によると、

『一部のiPhone、iPad、およびiPod touchの機種ではブラウズ履歴の保持期間が1か月になります。』とのことです。

検索してからある程度の期間が経っているため表示されなくなった、あるいはプライベートブラウズがオンになっていた可能性はありませんか？

iPhone でプライベートブラウズのオン／オフを切り替える - Apple サポート (日本)

新規検索とは文字通り、『🔍　検索/Webサイト名入力』欄に検索したい文字を入力し、一から検索することではないでしょうか？

こちらを試してみて、それでもうまくいかない場合はAppleサポートに問い合わせしてみてはいかがでしょうか。

iPhone や iPad でアプリが反応しない／予期せず終了する／開かない場合 - Apple サポート (日本)…4.アプリの削除は不要

お問い合わせ - Apple サポート (公式)