Dipende da come fai la ricerca.
Da dove arrivano i dati? Da un recordset?
Mostra il codice che usi per la ricerca...

Una cosa è certa, ad ogni ricerca devi svuotare e ri-popolare il LV.
Onestamente è la peggior implementazione in fatto di efficienza e praticità, anche se per 100 record può bassare.

Sarebbe più semplice, logico ed efficiente usare un DataGrid popolato da un ADODB.Recordset a cui, di volta in volta, imposti la proprietà Sort con il nuovo filtro.

Guarda questo progetto che permette all'utente di impostare un filtro multi-colonna 'al volo':
Progetti vari: DataGrid_FilterSearch
http://nuke.vbcorner.net/Progetti/VB...9/Default.aspx

e fa esattamente quello che serve a te.