Nem todos os desinstaladores são lentos. Os desinstaladores que são particularmente lentos são aqueles que criam um ponto de restauração do sistema (principalmente .msi), o que leva um tempo bastante longo. Os instaladores que acessam muito o registro também são um pouco mais lentos, já que o banco de dados não é tão bom assim.
Os desinstaladores que simplesmente desvinculam arquivos normalmente são muito rápidos, por outro lado.
No Ubuntu, os desinstaladores não fazem pontos de restauração do sistema nem acessam um registro para configurações. A maioria das configurações está contida em arquivos simples que são simplesmente desvinculados.
Editar : Caso alguém não esteja familiarizado com o termo "unlink", é o que realmente acontece quando você "exclui" um arquivo.
Uma boa descrição é encontrada na página de manual unlink do Linux :
unlink() deletes a name from the filesystem. If that name was the last link to a file and no processes have the file open the file is deleted and the space it was using is made available for reuse.
É por isso que os programas de recuperação podem encontrar arquivos que você excluiu há muito tempo. Se o espaço marcado como "disponível para reutilização" não tiver sido substituído, os dados poderão ser facilmente recuperados.