Ok, eu consegui encontrar minha própria solução (ironicamente) porque Gilles não estava se explicando corretamente e me fazendo pesquisar seus comentários enigmáticos.
Etapa 1: use dpkg -L $package
ou a caixa de diálogo Propriedades do Synaptic para encontrar o arquivo que não foi removido com o restante do pacote. Não sei por que um arquivo pode não ser limpo corretamente, mas é isso que causa esse problema. No meu caso foi /etc/avserver.conf.
Passo 2: instale o pacote ofensivo. Desta forma, o gerenciador de pacotes achará que resolveu o problema em si.
Etapa 3: execute sudo rm $offendingfile
para excluir o arquivo que o gerenciador de pacotes não deseja.
Etapa 4: limpe o pacote novamente. Todos os gerenciadores de pacotes reconhecerão que nada resta, porque tudo realmente desapareceu desta vez.
Exceto por esse rm, isso funciona com o Synaptic, para que eu possa me dar esses pontos de bônus.