Here is what I did:

michael@michael-desktop:~$ sudo ls /var/lib/dpkg/info/xem*
/var/lib/dpkg/info/xemacs21-mule.list
/var/lib/dpkg/info/xemacs21-mule.postrm
/var/lib/dpkg/info/xemacs21-support.list
/var/lib/dpkg/info/xemacs21-support.postrm


michael@michael-desktop:~$ sudo dpkg -l xemacs*
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name           Version      Architecture Description
+++-==============-============-============-=================================
un  xemacs-support <none>                    (no description available)
un  xemacs21       <none>                    (no description available)
un  xemacs21-bases <none>                    (no description available)
un  xemacs21-bin   <none>                    (no description available)
rc  xemacs21-mule  21.4.22-3.2u amd64        highly customizable text editor -
un  xemacs21-mules <none>                    (no description available)
rc  xemacs21-suppo 21.4.22-3.2u all          highly customizable text editor -
un  xemacs21-suppo <none>                    (no description available)
michael@michael-desktop:~$ 
michael@michael-desktop:~$ 
michael@michael-desktop:~$ sudo dpkg --remove --force-remove-reinstreq emacs
dpkg: warning: ignoring request to remove emacs which isn't installed
michael@michael-desktop:~$ sudo dpkg --remove --force-remove-reinstreq  xemacs-support xemacs21 xemacs21-bases xemacs21-bin xemacs21-mule xemacs21-mules xemacs21-suppo xemacs21-suppo
Package xemacs21-suppo listed more than once, only processing once.
dpkg: warning: ignoring request to remove xemacs-support which isn't installed
dpkg: warning: ignoring request to remove xemacs21 which isn't installed
dpkg: warning: ignoring request to remove xemacs21-bases which isn't installed
dpkg: warning: ignoring request to remove xemacs21-bin which isn't installed
dpkg: warning: ignoring request to remove xemacs21-mule, only the config
 files of which are on the system; use --purge to remove them too
dpkg: warning: ignoring request to remove xemacs21-mules which isn't installed
dpkg: warning: ignoring request to remove xemacs21-suppo which isn't installed
michael@michael-desktop:~$ 
michael@michael-desktop:~$ 
michael@michael-desktop:~$ sudo dpkg --purge --force-remove-reinstreq  xemacs-support xemacs21 xemacs21-bases xemacs21-bin xemacs21-mule xemacs21-mules xemacs21-suppo xemacs21-suppo
Package xemacs21-suppo listed more than once, only processing once.
dpkg: warning: ignoring request to remove xemacs-support which isn't installed
dpkg: warning: ignoring request to remove xemacs21 which isn't installed
dpkg: warning: ignoring request to remove xemacs21-bases which isn't installed
dpkg: warning: ignoring request to remove xemacs21-bin which isn't installed
(Reading database ... 339120 files and directories currently installed.)
Removing xemacs21-mule ...
Purging configuration files for xemacs21-mule ...
dpkg: warning: ignoring request to remove xemacs21-mules which isn't installed
dpkg: warning: ignoring request to remove xemacs21-suppo which isn't installed
Processing triggers for menu ...
michael@michael-desktop:~$ 

michael@michael-desktop:~$ sudo dpkg --configure -a
Setting up emacsen-common (2.0.3) ...
Install emacsen-common for xemacs21
emacsen-common: Handling install of emacsen flavor xemacs21
/usr/lib/emacsen-common/packages/install/emacsen-common: 29: /usr/lib/emacsen-common/packages/install/emacsen-common: xemacs21: not found
ERROR: install script from emacsen-common package failed
dpkg: error processing emacsen-common (--configure):
 subprocess installed post-installation script returned error exit status 1
Setting up dictionaries-common (1.12.10) ...
Install dictionaries-common for xemacs21
install/dictionaries-common: Byte-compiling for emacsen flavour xemacs21
/usr/lib/emacsen-common/packages/install/dictionaries-common: 64: /usr/lib/emacsen-common/packages/install/dictionaries-common: xemacs21: not found
ERROR: install script from dictionaries-common package failed
dpkg: error processing dictionaries-common (--configure):
 subprocess installed post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of ienglish-common:
 ienglish-common depends on dictionaries-common (>= 1.10.6~); however:
  Package dictionaries-common is not configured yet.

dpkg: error processing ienglish-common (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of iamerican:
 iamerican depends on dictionaries-common; however:
  Package dictionaries-common is not configured yet.
 iamerican depends on ienglish-common (= 3.3.02-5build1); however:
  Package ienglish-common is not configured yet.

dpkg: error processing iamerican (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of emacs24-common:
 emacs24-common depends on emacsen-common (>= 1.4.10); however:
  Package emacsen-common is not configured yet.

dpkg: error processing emacs24-common (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of ispell:
 ispell depends on dictionaries-common; however:
  Package dictionaries-common is not configured yet.

dpkg: error processing ispell (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of emacs23-common:
 emacs23-common depends on emacsen-common (>= 1.4.10); however:
  Package emacsen-common is not configured yet.

dpkg: error processing emacs23-common (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of aspell:
 aspell depends on dictionaries-common (>> 0.40); however:
  Package dictionaries-common is not configured yet.

dpkg: error processing aspell (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of emacs23-bin-common:
 emacs23-bin-common depends on emacs23-common (= 23.4+1-4ubuntu1); however:
  Package emacs23-common is not configured yet.

dpkg: error processing emacs23-bin-common (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of erlang-mode:
 erlang-mode depends on emacsen-common (>= 1.4.14); however:
  Package emacsen-common is not configured yet.

dpkg: error processing erlang-mode (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of aspell-en:
 aspell-en depends on aspell (>= 0.60.3-2); however:
  Package aspell is not configured yet.
 aspell-en depends on dictionaries-common (>= 0.49.2); however:
  Package dictionaries-common is not configured yet.

dpkg: error processing aspell-en (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of emacs24-bin-common:
 emacs24-bin-common depends on emacs24-common (= 24.1+1-2ubuntu3); however:
  Package emacs24-common is not configured yet.

dpkg: error processing emacs24-bin-common (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of emacs24:
 emacs24 depends on emacs24-bin-common (= 24.1+1-2ubuntu3); however:
  Package emacs24-bin-common is not configured yet.

dpkg: error processing emacs24 (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of emacs23:
 emacs23 depends on emacs23-bin-common (= 23.4+1-4ubuntu1); however:
  Package emacs23-bin-common is not configured yet.

dpkg: error processing emacs23 (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 emacsen-common
 dictionaries-common
 ienglish-common
 iamerican
 emacs24-common
 ispell
 emacs23-common
 aspell
 emacs23-bin-common
 erlang-mode
 aspell-en
 emacs24-bin-common
 emacs24
 emacs23
michael@michael-desktop:~$ 

michael@michael-desktop:~$ sudo ls /var/lib/dpkg/info/xem*
/var/lib/dpkg/info/xemacs21-support.list
/var/lib/dpkg/info/xemacs21-support.postrm