Well I finally managed to get rid of it! All I can say is that if apt had just tried good old dpkg -P ...
So in this case we see that apt is probably trying a remove + purge instead of a plain purge or something. # aptitude purge ~c The following packages will be REMOVED: iproute{p} 0 packages upgraded, 0 newly installed, 1 to remove and 29 not upgraded. Need to get 0 B of archives. After unpacking 0 B will be used. Do you want to continue? [Y/n/?] dpkg: warning: ignoring request to remove iproute which isn't installed # apt-get purge iproute Reading package lists... Done Building dependency tree Reading state information... Done The following package was automatically installed and is no longer required: linux-image-3.12-1-686-pae Use 'apt-get autoremove' to remove it. The following packages will be REMOVED: iproute* 0 upgraded, 0 newly installed, 1 to remove and 29 not upgraded. After this operation, 0 B of additional disk space will be used. Do you want to continue? [Y/n] dpkg: warning: ignoring request to remove iproute which isn't installed # dpkg -l iproute 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 +++-===============================-====================-====================-=================================================================== rc iproute 20121211-2 i386 networking and traffic control tools # dpkg -P iproute (Reading database ... 144149 files and directories currently installed.) Removing iproute (20121211-2) ... Purging configuration files for iproute (20121211-2) ... # dpkg -P iproute dpkg: warning: ignoring request to remove iproute which isn't installed Apt 1.0 -- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org