How to completely remove a package in Ubuntu (like it never existed)

When I remove a package in Ubuntu using apt-get remove package, it always seems to leave behind a lot of files... for example, log files in /var/log, config files in /etc, data in /var/lib, etc.

How do I COMPLETELY remove every trace of a package in Ubuntu, as if it never existed?

You should purge those packages.

apt-get purge somepackage

from man apt-get (APT-GET(8))

   purge
       purge is identical to remove except that packages are removed and purged (any configuration files are deleted too).

This is supposed to remove everything added by the package, such as config and data files. But I would assume it's possible that it generated something that is left behind anyway. dpkg doesn't track everything related to a package... and its cleanup scripts and such can be assumed to be imperfect and sometimes fail. Maybe it won't remove logs for example.