autoremove isn’t removing as much as you expect is that the packages which were installed automatically satisfy weak dependencies of other packages you already had installed. In your case,
dpkg-dev is already installed, itself as an automatic dependency; because it recommends the virtual
c-compiler package, any package providing
c-compiler will be kept after it’s installed.
Put another way, you have package A already installed with a weak dependency on package B, and package B isn’t installed. If you later install package C, with a dependency (strong or weak, but taken into account by
apt’s configuration) on package B, package B will also be installed, and marked as automatically installed. Removing package C however won’t cause package B to be considered for auto-removal, because package A keeps it “interesting” as far as
apt is concerned.
You could ask
autoremove to ignore weak dependencies (recommendations, by default), but that would probably cause a lot more packages to become removable than you’d expect or want.
I’m not aware of any good solution for this.
aptitude is somewhat more agressive in its automatic removals, but it doesn’t handle all situations either.
See How do recommends and suggests interact with apt-get dist-upgrade and apt-get autoremove? and Why did 'apt-get autoremove' not work properly? for more on this.