To begin chasing down a real, workable solution: The default SolutionCost is "safety, priority". I suspect the main problem here may be due to the unintended interactions of "priority" when there are/aren't removals involved, but do not have time to investigate further just yet *hint*.
-- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org