По какой логике apt помечает пакеты как вручную установленные?

gedit

видимо он не привязан жестко к гному, и для его работы достаточно gnome-common и еще пары-тройки либ
кто знает, может ты решил его оставить и юзать с другим ДЕ

такая логика подойдет?
а если она и правда такая у apt, то наверняка есть ключ для сноса вообще всего

Я не ставил сам gedit, если не ошибаюсь, он пришёл по зависимостям и должен был уйти. К тому же, я точно не ставил вручную gnome-common, и не вижу причин его отмечать вручную установленным.

google говорит, что нужно удалять с помощью:

sudo apt-get remove --auto-remove package

смысл меток в автоудалении.
если ты ставишь какой-то жирный метапакет, то почему бы не посмотреть зависимости и или отметить все зависимости как авто или некоторые вручную?

Для поплеваться проще на виртуалку что-нибудь накатывать.

Не проще, особенно, если речь идет о DE. Сейчас каждое первое DE использует OpenGL, 2D/3D-ускорение и прочие плюшки, которые в виртуалке работают через известное место. Первые релизы Gnome3 и KDE5 вообще отказывались в виртуалке запускаться, разрабы прямо указывали, что надо запускать на реальном железе.

По какой логике apt помечает пакеты как вручную установленные?

Все, кроме тех, которые притянулись по зависимостям. Т.е. и пакеты базовой системы (которые установились при инсталяции debian).

А ты поставил мета-пакет. Он включает в себя черти что. Пометь содержимое мета-пакета как автоматически установленные пакеты (авто — для авто-удаления). После этого сделай autoremove.