Предлагаю по возможности добавить в сборочницу ключик, который бы добавлял на пересборку (rebuild) пакеты, ставшие при первой/очередной сборке задания неустанавливаемыми из-за unmet'ов.  Даже название придумал: --autorebuild.

В нулевом приближении можно брать имена в алфавитном порядке, во втором -- по уменьшению времени сборки пакета (buildtime/ctime); в третьем -- по графу BR (возможно, bircoph@ проконсультировал бы по revdep-rebuild) и вот такой код было бы здорово иметь и для обычных task add/build (--autosort?).