Distro-maintained packages (not just .Deb but rpm, pacman, etc) do fulfill this, but generally not via an automated means. It relies on package maintainers manually testing or reading source code to figure out what to remove. They don't just blindly accept whatever uninstall script comes with the software.
They don't remove everything, but I consider their choices generally sane. I.e. there are good reasons to not remove Postgres' data when Postgres is uninstalled. People would be pissed if they tried to switch from Ubuntu's packaged version to somebody else's Postgres repo, and Ubuntu deleted all their data when their Postgres was removed.
Linux has the functionality to do this via stuff like fanotify or kernel extensions like selinux. I don't believe this is an issue of "can't be done", I think it's an issue of "distro maintainers do a pretty good job and selinux is clunky". Windows and MacOS might as well; I don't know enough to say either way.
I think Windows has a particularly hard job here because of the proliferation of proprietary binaries, where they can't audit the source code even if they wanted to. Most stuff in Linux repos is open source and can be audited, and I think (could be very wrong) Google Play and the App Store expect to be provided with source code so they can do their own build.
