Secure deletion and trash bin support

Given users a and b, in group C, where (all paths filesystem-relative):

/ is writable by user a, with the sticky bit on, and readable and
executable by everyone (of course).
/bar is writable by group C.
/baz is writable by user b only, and not readable by anyone else.
/foo is writable by user x, who is known to be a bit of a mischievous sod,
and not by user b.

User b deletes a file in /bar. Now presumably /.trash inherits its
permissions from /, right? Well, that file's just gone into /.trash, which
*b cannot delete files from*. So now user b can fill up the disk just by
creating and deleting files, but has to appeal to a to fix things.

Worse, files b delets in /baz can only be deleted from /.trash by user a,
even though user a *cannot delete them from /baz in the first place*.

But it gets nastier. What if user a deletes an important file and then
user x spots this and immediately afterwards deletes a file with the same
name from /foo? Does that file overwrite the important file in /.trash? Do
the files in /.trash get the directory name encoded in their filename
somehow, to evade this? (If so, that means you can break the system in
another way: the encoding for filenames must, if not ambiguous, sometimes
be longer than the filenames themselves. Thus it's possible to produce a
file in a deeply-nested directory which has a name which is too long, when
encoded, to be written to /.trash.)

Another scenario: user b deletes an important file out of /baz: it was
group-readable, but what the hell, it's in a directory they can't read
anyway. But now it's been deleted, that is no longer true: now user x can
read it. Worse, user x can hardlink it into his own directory, and b can't
do anything about it: can't even delete it again. However, it is possible
depending on the semantics of repeated deletion that he may be able to
*overwrite* it by deleting another file with the same name (in which case
deleting symlinks seems risky, as that's opened up an rm variant of the
classic symlink attack: delete a symlink to /etc/passwd, wait for root to
delete a file with the same name, oops: worse, an attacker with write
privs in /.trash can delete anyone's file by hardlinking it into /.trash
under a suitable name and waiting for someone to delete a suitable file:
no, overwriting is not safe, you must unlink()).

And then what happens if you flip on the immutable bit for files
in /.trash?

So now we have rm(1) not consistently trashing files, possibly leading to
unreadable-by-others files becoming readable by them and unremovable by
you, or alternatively leading to arbitrary files that happen to have
symlinks pointing to them or happen to have been hardlinked into or out
of /.trash being overwritten.

This proposal needs a *lot* of thought. Either /.trash is fantastically
magical and violates most Unix rules for file access (hardlinks out of and
into banned, *symlinks* out of and into banned, always 1777 except that
files belonging to other users don't appear, um, how will that work
exactly?) or you've opened a vast can of worms.

(A plan9-style per-user /.trash bind-mount might work better, but the
userspace infrastructure for that is not really there yet.)