apt-get purge has stopped working for removed packages

Output has changed, but that's a duplicate of bug 244598 otherwise.

That's most odd, because unlike the suggestion in #244598, this was working fine for me until I upgraded to natty...

OK, it turns out that bug #244598 was in fact fixed in apt 0.8.0, but seems now to have reappeared.

This bug was fixed in the package apt - 0.8.15ubuntu1

---------------
apt (0.8.15ubuntu1) oneiric; urgency=low

  * merged from debian-unstable, remainging changes:
    - use ubuntu keyring and ubuntu archive keyring in apt-key
    - run update-apt-xapian-index in apt.cron
    - support apt-key net-update and verify keys against master-keyring
    - run apt-key net-update in cron.daily
    - different example sources.list

apt (0.8.15) unstable; urgency=low

  [ Julian Andres Klode ]
  * apt-pkg/depcache.cc:
    - Really release action groups only once (Closes: #622744)
    - Make purge work again for config-files (LP: #244598) (Closes: #150831)
  * apt-pkg/acquire-item.cc:
    - Reject files known to be invalid (LP: #346386) (Closes: #627642)
  * debian/apt.cron.daily:
    - Check power after wait, patch by manuel-soto (LP: #705269)
  * debian/control:
    - Move ${shlibs:Depends} to Pre-Depends, as we do not want APT
      unpacked if a library is too old and thus break upgrades
  * doc/apt-key.8.xml:
    - Document apt-key net-update (LP: #192810)

  [ Christian Perrier ]
  * Galician translation update (Miguel Anxo Bouzada). Closes: #626505
  * Italian translation update (Milo Casagrande). Closes: #627834
  * German documentation translation update (Chris Leick). Closes: #629949
  * Catalan translation update (Jordi Mallach). Closes: #630657

  [ David Kalnischkies ]
  * fix a bunch of cppcheck warnings/errors based on a patch by
    Niels Thykier, thanks! (Closes: #622805)
  * apt-pkg/depcache.cc:
    - really include 'rc' packages in the delete count by fixing a
      typo which exists since 1999 in the source… (LP: #761175)
    - if critical or-group can't be satisfied, exit directly.
  * apt-pkg/acquire-method.cc:
    - write directly to stdout instead of creating the message in
      memory first before writing to avoid hitting limits
    - fix order of CurrentURI and UsedMirror in Status() and Log()
  * apt-pkg/orderlist.cc:
    - let VisitRProvides report if the calls were successful
  * apt-pkg/deb/dpkgpm.cc:
    - replace obsolete usleep with nanosleep
    - remove invalid pkgcache.bin and rebuild it if possible
    - log reinstall commands in history.log
  * debian/apt{,-utils}.symbols:
    - update both experimental symbol-files to reflect 0.8.14 state
  * debian/rules:
    - remove unused embedded jquery by doxygen from libapt-pkg-doc
  * cmdline/apt-mark.cc:
    - reimplement apt-mark in c++
    - provide a 'showmanual' command (Closes: #582791)
    - provide a 'dpkg --set-selections' wrapper to set/release holds
  * cmdline/apt-get.cc:
    - deprecate mostly undocumented 'markauto' in favor of 'apt-mark'
  * cmdline/apt-cache.cc:
    - deprecate mostly undocumented 'showauto' in favor of 'apt-mark'
  * apt-pkg/pkgcache.cc:
    - really ignore :arch in FindPkg() in non-multiarch environment
  * doc/po/de.po:
    - undo the translation of the command 'dump' in manpage of apt-config
      as report by Burghard Grossmann on debian-l10n-german, thanks!
  * apt-pkg/deb/debmetaindex.cc:
    - do not download TranslationIndex if no Translation-* will be
      downloaded later on anyway (Closes: #624218)
  * test/versions.lst:
    -...