¿Has probado a reindexar los productos? El índice de búsquedas debería irse regenerando conforme se van añadiendo productos, pero por experiencia te digo que no es así.
Ve al menú Parámetros de la tienda -> Buscar, y reconstruye el índice de búsquedas completo. Luego, si puedes crear una tarea CRON como te indica ahí, mucho mejor. Si no, recuerda acceder de vez en cuando (especialmente después de añadir productos nuevos), y regenéralo de forma manual: