Why does "apt-get autoremove sendmail" leave dependencies behind?

I have noticed that installing sendmail, then uninstalling it, using apt-get will leave many unwanted files behind.

sudo apt-get install sendmail
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following extra packages will be installed:
  liblockfile-bin liblockfile1 make procmail sendmail-base sendmail-bin
  sendmail-cf sensible-mda
Suggested packages:
  make-doc sendmail-doc rmail logcheck resolvconf sasl2-bin
Recommended packages:
  default-mta mail-transport-agent fetchmail
The following NEW packages will be installed:
      liblockfile-bin liblockfile1 make procmail sendmail sendmail-base
      sendmail-bin sendmail-cf sensible-mda
0 upgraded, 9 newly installed, 0 to remove and 0 not upgraded.
Need to get 2256 kB of archives.
After this operation, 5263 kB of additional disk space will be used.
Do you want to continue? [Y/n] y

So we installed sendmail - 9 new packages and 5.2MB.
Minutes later, I changed my mind and want to uninstall it. No problem, apt-get got me covered, right? I purge (delete package and package configuration files):

sudo apt-get purge sendmail
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
  procmail sensible-mda
Use 'apt-get autoremove' to remove them.
The following packages will be REMOVED:
  sendmail*
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
After this operation, 219 kB disk space will be freed.
Do you want to continue? [Y/n] y

Then autoremove (remove automatically installed package dependencies)

sudo apt-get autoremove sendmail
Reading package lists... Done
Building dependency tree
Reading state information... Done
Package 'sendmail' is not installed, so not removed
The following packages will be REMOVED:
  procmail sensible-mda
0 upgraded, 0 newly installed, 2 to remove and 0 not upgraded.
After this operation, 550 kB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 24702 files and directories currently installed.)
Removing sensible-mda (8.14.4-8+deb8u1) ...
Removing procmail (3.22-24) ...
Processing triggers for man-db (2.7.0.2-5) ...

That's 219 + 550 = 769KB recovered! Did I just loose 4.something MB of space? For what?

Upon looking closely at the output, it appears that apt-get removed only 3 of the package that it previously automatically installed. Package sendmail-base, for example, remains:

sudo apt-get remove sendmail-base
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages will be REMOVED:
  sendmail-base sendmail-bin
0 upgraded, 0 newly installed, 2 to remove and 0 not upgraded.
After this operation, 2464 kB disk space will be freed.
Do you want to continue? [Y/n]

So there is some of my wasted space. But why are these automatically installed dependencies still installed?

Solution 1:

sendmail is a meta package consisting of a set of dependencies. When you install the sendmail metapackage it installs sendmail-bin, amongst other things. This provides a recommended package for cron, for example, but I believe there are also some other packages that recommend packages in the sendmail dependency chain.

Autoremove will not remove auto packages which are recommended by other packages. You can change this behaviour by, for example, adding this apt configuration in /etc/apt/apt.conf.d/99_norec

APT::AutoRemove::RecommendsImportant "false";
APT::AutoRemove::SuggestsImportant "false";

Then run apt-get remove --auto-remove sendmail, and you should see all your sendmail dependant packages being marked for removal, along with some other unrelated things which are now removal candidates due to the overall change in the apt configuration.

Though, I believe this is not recommended (no pun intended). You should deal with these manually if you need to get rid of them.