TL;DR or "Just scorch my pi"
sudo apt-get remove --auto-remove --purge 'libx11-.*'
sudo apt-get autoremove --purge
(Repeat apt-get autoremove --purge until no orphans remain)
Further explanation
If a package foo depends on another package libfoo and you remove the libfoo package, the dependent (foo) is also removed. Because Foo has a depends line specifying libfoo, it would be broken to leave foo if libfoo were removed. The reverse is not true: removing foo does not delete libfoo automatically. Another package xfoo may also depend upon libfoo, so apt won't just remove it (although apt will track if it was installed only as a side-effect of installing foo and offer to auto-remove it if you ask it to, so long as no others still depend on it)
Meta packages depend on a set of other packages in much the same way that foo depended on libfoo, so when you remove a meta-package, little else is typically removed. For example, there may be two meta-packages that depend on xterm (lxsession and xfsession perhaps), but uninstalling one or both won't uninstall xterm because xterm isn't broken without lxsession or xfsession. Meta-packages are generally at the top of the dependency tree, not at the bottom, and few things tend to depend directly on meta-packages. Meta-packages primarily provide a convenient way to install a sensible set of packages at once, but they aren't uninstall tools.
So, if you want to scorch everything that depends upon X11, you will need to target the base set of libx11 libraries that all x11 apps must ultimately depend upon:
sudo apt-get remove --dry-run --auto-remove --purge 'libx11-.*'
sudo apt-get autoremove --dry-run --purge
This will (simulate) remove everything that ultimately depends on libx11-.*, and will also remove any packages that were installed as a dependency of an X11 program even if they didn't directly depend on X11 itself (CUPS and Ghostscript are typically installed as a side-effect of installing a desktop environment). The second command will remove subsequent orphans until none remain. Remove "--auto-remove" if you want to do this step later or not do it at all, or just add back the packages manually after cleaning the GUI off.
Remove the --dry-run option to actually perform the operation after you have checked that it won't remove packages you did not intend to be removed.)
I prefer to clean and purge the side-effects, and add them back as needed. Also, I went ahead and tested this on my own pi, and it rebooted to a very spartan but functional server. :)
Why does a remove install something?
The above strategy solves the stated problem, but there is still the curiosity of why a remove operation results in packages being installed.
At the heart of every package manager is a satisfiability solver of some kind. When you tell a package manager to install some packages, remove some packages, or upgrade some packages, what you are really asking it to do is to solve for the next desired state of software installation given an available set of packages. This solution may include installing additional packages (dependencies), removing existing packages (conflicts, breaks), downgrading/upgrading specific packages (compatibility level), or a combination thereof. So, while it is a bit counterintuitive that the solver determines that some packages need to be installed in order for other packages to be removed, it makes perfect sense. This is the nasty dependency management problem that package managers solve.
A concrete example: Given a set of Java applications already installed, they all depend upon a java compatible runtime which currently happens to be openjdk-7-jre. You then ask the package manager to solve for installation of a new Java tool that declares a conflict with openjdk-7-jre but works with oracle-7-jre (both packages generically provide a java-7-runtime). The solver will propose a removal of openjdk-7-jre and an install of oracle-java-7-jre as the solution to your desired state of having the new package installed while not breaking existing packages.
In this specific case, xterm is a package that provides a virtual dependency called x-terminal-emulator (xterm, lxterminal, and aterm all provide an x-terminal-emulator), so it is likely that in removing lxterminal (as a part of removing lxde), the solver found an existing installed package (transcode as a possible example) that required some kind of x-terminal-emulator, so the solver chose to install xterm (which requires libutempter0 and xbitmaps, explaining the other packages to install) to satisfy the otherwise broken dependency. Without seeing the package database, I would hypothesize that this is the most likely scenario.
To discover the packages that are currently depending upon xterm (or an alternate), use the apt-cache rdepends command (using the --installed switch to limit to installed packages only):
$ apt-cache --installed rdepends xterm
xterm
Reverse Depends:
|xorg
clusterssh
|xinit
|tk8.5
|tk8.4
|transcode
Dependencies that start with the alternation character '|' mean that the package depends on xterm or something it provides (that something is x-terminal-emulator in this case). The clusterssh package depends on xterm explicitly, and does not allow for an alternative. This is the short list of the packages that are causing xterm to be required.
What about deborphan?
The functionality of tracking orphans was incorporated into apt-get via the 'autoremove' functionality in 2010 (Debian bug 582791) rendering deborphan mostly redundant and essentially obsolete. Unlike deborphan and other solutions like it, apt-get directly tracks which packages were explicitly installed and which packages were installed as a side-effect or dependency of an explicitly installed package. For example, if an administrator installs foo, libfoo is installed as a side-effect and apt-get autoremove will, in fact, remove libfoo if autoremove (or --auto-remove) is specified when removing foo.
The approach taken by deborphan is a collection of guesses. For example, the guess that an installed library that does not have a dependent must be an orphan: If libfoo is installed, but neither foo nor xfoo are, deborphan may decide it must be an orphan. One failure mode here is that libraries might be specifically installed for the tools they provide (libxml2 for xmllint before it was repackaged into libxml2-utils) or simply available for development purposes. Such packages are not orphans. Additionally, deborphan focuses on libraries, so it misses a number of non-library orphans that apt tracks (Obsolete packages vs. orphaned packages).
