Mit aptitude geht's? apt-get verweigert das --purge nämlich mit der Begründung, das Paket sei nicht installiert.