Parece ser que desde la versión 1.3.2.4 a la 1.5.1.0 Magento viene con un pequeño bug por el cual la búsqueda no funciona y no devuelve resultados.

El primer paso es reindexar todo por si esto lo solucionara (casi nunca lo soluciona)

Si esto no funciona, desafortunadamented la solución pasa por modificar un fichero del core.

El fichero que hay que editar es app/code/core/Mage/CatalogSearch/Block/Result.php

Descomentar la linea 149 y 150

$this->getListBlock()
->setCollection($this->_getProductCollection());

Modificar la linea 172

$this->_productCollection = $this->getListBlock()->getLoadedProductCollection();

por esta

$this->_productCollection = Mage::getSingleton('catalogsearch/layer')->getProductCollection();

Una vez está esto parcheado solo nos queda reindexar y la búsqueda debería volver a funcionar.