↓のページで作成しているデータ、ユーザーフォームを使って
お書きいただいたコードをコピペして実行してみました。
http://www.eurus.dti.ne.jp/~yoneyama/Excel/vba/vba_listbox.html

ユーザーフォームのコンボボックスの名前を cmb区分　の変更しただけです。

cmb区分　には氏名のカタカナが相当していますので、コンボボックスのみを空欄にして実行しましたが
エラーは発生しませんでした。
テキストボックス1〜3のうち検索には1と3の値だけが使用されているみたいなので、
テキストボックス1と3に入力して、コンボボックスはDeleteキーで削除して空欄にして実行。
テキストボックス1だけに入力してコードを実行。
テキストボックス3だけに入力してコードを実行。
コンボボックスで1つだけ選択してコードを実行。
いずれもエラーは出ませんでした。

こちらはExcel2016で実行して確認してみましたが、データが異なるためか
お書きのエラー↓が再現できませんでした。
> その際に検索画面でコンビボックスやテキストボックスを空欄にして検索すると、「インデックスが有効範囲にありません。」と表示されてしまいます。

ファイルをこちらに提供して頂くことが可能でしたらメールでお送りください。
分かるかどうかは断言できませんが・・・・