Si te ocurre el problema de que el buscador no encuentra los productos cuando has introducido una cifra importante de estos, hay que reindexar todos los datos, para ello vamos a:

Sistema->Index Management

Seleccionamos todas las filas y

en Acciones seleccionamos Reindex Data

despues pulsamos Enviar!

Después del rato que se tira indexando nos vamos a nuestra homePage de Magento, escribimos cualquier busqueda y Vualá!! magento a encontrado un montón de resultados.