Yep, I've already thought of it in the several minutes after posting it. If it were possible to make a hardlink to a directory, my solution for a directory with a varying set of files would be:

1) hardlink all the files from the old directory ("foobar") into a temporary new directory ("foobar_tmp1"),

2) create a hardlink ("foobar_tmp2") to the old directory ("foobar"),

3) rename the new directory ("foobar_tmp1") to the old directory's name ("foobar"),

4) patch the "old" directory ("foobar" now linking to the shrunk directory) with the new files in "foobar_tmp2",

5) get rid of "foobar_tmp2".

Still doesn't take care of all possible issues such as a program creating a file in "foobar" between steps 2) and 3) and reopening it very quickly after step 3), but at least it seems to avoid the issue of lost files.

Sadly step 2) seems impossible. I still believe the original version should be transparent for a directory with a fixed set of files, but of course very large directories probably have a higher chance on average of their set of files changing in a short period of time. That may or may not be a problem.

EDIT: Maybe a mandatory lock on the directory around the original step 2) with an additional check whether the directory's file set didn't change would work on Linux, if such a thing works the way I think it does (quite possibly it doesn't).