Fedora 12 and unprivileged package installation

I think that's half-right. You want the /var/usr/$USER idea, sure, but it
is bind-mounted by pam_mount into a per-user private mount, maybe /usr/usr
(ew, maybe somewhere else) and *that* is what is referenced in PATHs.

(Most of the rest of your post is talking about problems that GNU stow and
graft and other similar systems have long considered and solved. Suffice
to say that systems built from symlink farms are quite practical. Hell,
systems built from symlink farms *at runtime*, so users can have per-user
and even per-session package selection are practical, although the farm
construction might take a second or two. I've implemented a couple of
systems like that myself...)