The problem with mandating self-contained applications is that there are some useful features associated with applications that are INHERENTLY not self-contained. Shell integration is a good example, but basically any kind of integration or shared functionality (or even data) with the system or with other applications falls in this category.
The manifest approach described by Miguel could be a good compromise, but it's not immune to problems.
Obviously no piece of software is self-contained. It has to make use of some sort of resources and interact with the user in some way. For a sandboxed platform, you carefully design the APIs to not grant any unintended privilege to apps. You can still do all sorts of fancy integration, you just do it through an airtight API.
It does that with a completion script, typically put in /etc/bash.completion.d. All scripts in this directory are sourced by /etc/bashrc. Each app provides its own completion script.
The packaging system (RPM, deb) tracks files installed anywhere on the filesystem, including ones in /etc/bash.completion.d/, and will remove all of them when the application is uninstalled. "Symlink magic", whatever that is, won't help at all.
I know that the package manager keeps track of it. I did not express myself clear enough.
> The packaging system (RPM, deb) tracks files installed anywhere on the filesystem, including ones in /etc/bash.completion.d/, and will remove all of them when the application is uninstalled. "Symlink magic", whatever that is, won't help at all.
If all the files needed for a package / program are in one place, the job of the package manager gets easier.
You might want to have a look at GoboLinux. They are trying to make the file system the package manager. (Haven't used it, yet, though. Still using a Linux with a traditional package manager.)
The manifest approach described by Miguel could be a good compromise, but it's not immune to problems.