This is an attempt to submit brainstorm 10644 as a workable idea, that will actually achieve the goals elie stated.
Modify the install process to use one of three privileged accounts, as follows:
1. Any package which needs to install something suid, or needs to touch /etc, /bin, /lib, or /var (excluding, of course, the actual package files) still requires root to install. (Simple heuristics: If it's not all going in /usr, it touches root so requires root. Only root can su without a password, so suid requires root.)
2. Any other package can either be installed using the 'bin' user or using the 'local' user. If it's installed using the 'bin' user, it is put into /usr, the way most packages are installed today.
3. If it's installed using the 'local' user, it's installed into /usr/local. (The only change from the current paths is that 'local' is inserted right after /usr; the structure otherwise is retained.) Any package installed using the 'local' user tracks which user installed it. Only that user or someone with either 'bin' or 'root' access can uninstall it.
With this setup, one could then use sudo(1) or a similar program to manage who can install programs, and at what level. Note that dpkg would need to some modifications. One possibility could be have it store the package database information with acls to allow both 'bin' and 'local' update it. (This could be simplified slightly by having 'bin' own the database.)
There would need to be some key constraints:
A. Only root could install files without entering a password to do so.
B. The 'bin' and 'local' users would need a shell that prevents general command execution. I'd recommend a custom shell which invoked aptitude, synaptic, or another package manager depending on environment and what is installed.