Se o arquivo ou pasta não estiver dentro do diretório pessoal de um usuário, ele poderá ser removido nos scripts de mantenedor do pacote ( postrm seria adequado), de preferência apenas na remoção, não na remoção "simples".
Existe um precedente para isso, vários pacotes no Debian possuem scripts de pós-remoção que excluem arquivos que eles criam no tempo de execução (não em seus scripts de pós-instalação) quando são removidos; por exemplo, alsa-utils remove seus arquivos de estado, amavis remove todo o seu estado ...