First thing that comes to my mind is a PAM plugin that generates a new root directory for the user when they log in, named something sane under a fixed hierarch

First thing that comes to my mind is a PAM plugin that generates a new root directory for the user when they log in, named something sane under a fixed hierarchy. A recursive walk can later pick them all up and clean up.