После индексации все товыры находит?Проиндексировано товаров "всего на сайте / найдено"?
Нужно разрешить заказывать товары с нулевым количеством.
В настройках поиска в Вес - Вес атрибута и Вес характеристик установите самый малый.