From dpkg man page:
--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).
So you didn't remove completely the zsh
, but some information remained into the system. The status the package will be "d" (removed) and not "p" (purged or never seen).
You need to purge the package to remove also the conffiles, so to reinstall the packages as new.
Note: if you are curious, you can check /var/lib/dpkg/
to see what the system knows about your packages.