Eu resolvi meu próprio problema. Embora eu não recomendaria isso, depois que todos os processos de desinstalação falharam, eu finalmente cedi e localizei manualmente todos os arquivos remaning que tinham alguma coisa a ver com o pure-ftpd e removi todos manualmente, então isso permitiu que a remoção fosse concluída.
Usando o gerenciador de arquivos Webmin, fiz uma busca por tudo que correspondesse a pure-ftpd, pure-ftpd-mysql e pure- e excluísse todos eles. Havia cerca de 66 arquivos ainda restantes.
Eu já consegui reinstalar com sucesso o pure-ftpd