Пётр, вообще говоря пример совсем не корректен.

Во-первых, и это только верхушка айсберга: действия install и remove-autoremove не являются на 100% противоположными. Это всё потому, что в Debian существуют мягкие зависимости между пакетами.

Допустим, поставили Вы пакет А, у которого был в recommends пакет X, но который Вы, в силу некоторых причин, на тот момент дали указание не ставить. Затем, спустя, какое-то время Вы про пакет X уже и думать забыли. И вот Вы ставить пакет B, который по зависимостям тянет X в том числе. После этого, если Вы решите снести пакет B через remove-autoremove, пакет X останется в системе, как ни крути, ибо пакет A от него всё-таки зависит.

А во-вторых, и это основной момент, где Вы лопухнулись: kde -- это мета-пакет, который тянет кучу других, помечая их как manually-installed. Это делается потому, что была целая куча баг-репортов о том, что пользователи удаляли мета-пакет, и у них следом удалялось полсистемы, связанные с тем же kde/gnome2 и другими DE, для которых существовали мета-пакеты.

Потому естественно при такой последовательности действий у Вас осталось дофига всего. Существенно, что это НЕ проблемы пакетного менеджера, а проблемы, собственно, самих пакетов.