Using dpkg to test if a package was uninstalled was racy and error
prone: once really completely removed, dpkg don't have any reference of
the package in its database anymore. The 'deinstall' dpkg state is only
temporary, so we can not really rely on it to know if a package is
removed. Let's use 'apt-cache policy' rather.

Refs: #14596