Андрей, Артем, спасибо!
Лазить в базу - это да это самое-самое последнее дело на крайний случай
Они не только не удалялись, но еще и не работали до этого.
Посмотрели в системных заданиях - увидели много интересного: зависшие бизнес-правила и не выполненные задания по поиску.
Ошибку удалось ликвидировать. Похоже, причина была в куче зависших бизнес-правил именно на тех объектах, на которые настраивались правила поиска.