Excellent question.. yes, we actually remove the account and pkill any existing sessions owned by the user. The OS might reuse UID's if it wishes. This will cleanly work over NFS as well. (On the server side as well, as long as the NFS server respects POSIX file locking semantics.) The agent (shim) is only a few hundred lines of readable Python that just scripts standard Linux commands, so it plays nicely with other tools -- even other logging or user management tools, PAM modules, etc. Also, the shim won't touch any user accounts that it didn't create (tagged in the comment field), so existing system or backup accounts are safe and won't ever be touched.
If the software doesn't manage UIDs internally then this is a recipe for disaster because keeping UIDs in sync is a PITA. It's a waste of time to do manually, but an even bigger waste of time to have to fight with the OS to get it right. If you're using NFS then you're screwed.
Usernames are one-for-one correlations with UID, so just don't allow users to personally owning files outside of their /home (they shouldn't according to FHS/LSB/POSIX/etc).
Here's the source code: https://github.com/userify/shim/blob/master/shim.py#L161