Haben Sie evtl. daran gedacht den Suchindex neu aufzubauen?
In Magento bis Version 1.3.x finden Sie die Funktion zum Aufbau des Suchindex unter: System > Cache Verwaltung > Suchindex > NEUAUFBAU.
Ab Magento Version 1.4.x gibt es einen eigenen Navigationspunkt zum Aufbau der diversen Indexe: System > Index Verwaltung > Katalog Suchindex > Neuaufbau