Da página de manual do dpkg:
--remove package (...) Remove an installed package. This removes everything except conffiles, which may avoid having to reconfigure the package if it is reinstalled later (conffiles are configuration files that are listed in the DEBIAN/conffiles control file).
Você não removeu completamente o zsh
, mas algumas informações permaneceram no sistema. O status do pacote será "d" (removido) e não "p" (removido ou nunca visto).
Você precisa limpar o pacote para remover também os conffiles, para reinstalar os pacotes como novos.
Nota: se você está curioso, pode verificar /var/lib/dpkg/
para ver o que o sistema sabe sobre seus pacotes.