Creo entender tu problema , cuando vos pulsas el botón buscar el proceso es tan rápido que no llegas a ver el mensaje que vos queres. Suponiendo el método clásico de un label que lo pones en visible e invisible.
En este caso lo que te conviene es detener el proceso por un instante luego de presionar el botón buscar.
Seria algo así:
Public sub Boton_Buscar()
call Esperar Tiempo
call Comenzar_Proceso_de_Búsqueda
label1.caption="Busqueda Finalizada"
end sub
Public Sub Esperar Tiempo()
Dim Tiempo As Date
Tiempo = Time
Tiempo = DateAdd("s", 10, Tiempo)
Do While DateDiff("s", Time, Tiempo) > 0
label1.caption="Buscando..."
DoEvents
DoEvents
DoEvents
DoEvents
Loop
End Sub
Espero que sea de ayuda!