Раз всё упирается в трудности с отслеживанием зависимостей сирот в списке потенциальных сирот, пусть Магия сама отслеживает эти зависимости по шагам.
Предлагаю удалять выбранные пакеты без зависимостей через rpm -e --nodeps имя_пакета. В теории мы получаем результат, сходный с работой CCleaner, когда за один проход он гарантированно удаляет отмеченные ключи реестра, но не удаляет связанные с ними. При повторном сканировании он выдаёт список оставшихся от удалённых. Там приходится запускать анализ/очистку несколько раз, поскольку каждый раз он выдаёт всё меньше и меньше зависимостей (ключей). Обычно 2-3 прохода бывает достаточно.
Таким образом, если логика работы urpmq --auto-orphans вернА, мы пошагово приблизимся к идеалу чистой системы, просеивая зависимости сирот через сито rpm. Этот вариант раза в 3 быстрее, чем urpme --auto имя_пакета и позволяет более детально исследовать зависимости пакетов. Что скажете?
p.s. Сам процесс удаления становится более динамичным и предсказуемым. Для тестов выложена версия 1.3. Истина где-то рядом. ))