Apt-get doesn’t completely uninstall dependencies which it has installed

You asked a few different question here, I hope I can at least help on one or two.

To list all installed packages, use dpkg to output in a field separated list

dpkg -l 

To just get the package list, without extra fields, so you can pipe it elsewhere.

dpkg -l | awk '{print $2 }' # Pipe to grep after the awk, or glob from dpkg

For example, if I want to remove an old kernel,

apt-get purge `dpkg -l linux* | awk '{print $2}' | grep 3.0.0-12`

The easiest way to go through all unneeded dependencies, is with debfoster. It runs interactively and goes through what you want, their dependencies and can remove or list what is not a recursive dependency.

To list all recursive dependencies of a specific package,

debfoster -d $PACKAGE ## PACKAGE is the specific package.

After you have executed debfoster you can check any dependents a package has also,

debfoster -e $PACKAGE ## PACKAGE is the specific package.

A really great way to list 'orphaned' packages, is with deborphan. Run deborphan without options, and it will list all 'orphaned' packages. An 'orphan' is a package that nothing depends on, and you have not explicitly installed.

I also like to clean any 'orphaned' packages, after a fresh install. After I have removed specific packages, you can get anything missed by apt-get autoremove --purge with,

apt-get purge `deborphan`

Finally sometimes you don't --purge and end up with package 'leftovers', the newer versions of apt-get can automatically remove them. To remove all 'leftovers' from uninstalled packages run,

apt-get autoclean

If you don't have the new version of apt-get, you can always remove them with these commands. They error if no 'leftover' files exist, it seems like autoclean can miss some occasionally regardless.

dpkg --list |grep "^rc" | cut -d " " -f 3 | xargs dpkg --purge

A slight variation on Installing packages by importing the list with dpkg --set-selections should do the trick.

Save the list of packages on your reference system:

dpkg --get-selections > packages.lst

Then install packages based on that list on your target system, after updating the list of available packages:

dpkg --merge-avail <(apt-cache dumpavail)
dpkg --clear-selections
dpkg --set-selections < packages.lst
apt-get dselect-upgrade