もしもPCの復元データに検索落ちの原因があるなら
復元の際に新しいiPhoneとして復元しなきゃダメだぞ。
以前に同期したiPhoneで復元するとPCの復元データで復元される。

でもそれだとアプリのデータ全部消えるから
まずは設定→Safari→「Cookieとデータを消去」と「履歴を消去」かな。
それでダメなら設定→一般→リセット→「ネットワーク設定をリセット」するくらい。
それでもダメなら新しいiPhoneで復元する。