I've been suggested to split the bug into two. I'll let this one deal with regenerating apt-file cache and I've filled new one to deal with extra cleaning. http://bugs.debian.org/636489