I've been playing with a solution for this on Branch_1_4_0, at least with pessimistic locking. Basics are:
1) TreeCache._remove should not be calling node.releaseAll -- releasing locks should be the task of the interceptors, not the cache.
With that in place the IdentityLock held by the removed node can still function as a guard for that Fqn. Problem now is how to force threads to acquire that lock after the node itself is no longer in the tree.
2) PessimisticLockInterceptor maintains a Map<Fqn, DataNode> removedNodes. PLI.invoke() checks if its a remove call; if it is, the lock() method is instructed to put the Fqn and DataNode in the map. (Done in lock() because it's the method that finds the DataNode in the tree).
3) If a tx is in effect, besides storing the node in the removedNodes map, it's Fqn is also stored in a list in the TransactionEntry. This list is used at tx commit/rollback to remove the entries from the removedNodes map. If a tx is not in effect, the entry is removed from the removedNodes map when the invocation returns. 
4) Other methods, when they are in lock(), if they can't find a node in the cache to lock, before creating a new one they first do a lookup in the removedNodes map. If they find a node there, they try to acquire the lock on it. Only when that lock is acquired do they continue on to the regular code that find/creates/locks the node in the cache. Thus they block until the tx that removed the node commits.
4) If a lock is obtained on a node from the removedNodes map, the lock is stored in the LockTable or TransactionEntry, the same as any other lock. Thus is gets released the same as any other lock.
With this, the unit tests I added for JBCACHE-871 pass. I haven't checked if all sorts of other tests break. I also haven't given any thought to optimistic locking.
One note -- let's say there is a tree /a/b/c, and a tx removes /a/b (and thus c as well). An entry for /a/b is put in the map, but not for /a/b/c. This is because any other thread wanting to touch /a/b/c will have to traverse /a/b, so the locking there is sufficient, as long as READ_COMMITTED or stronger is in effect. Weaker than that and this isn't an issue anyway.
 This bit of removing the entry from the map on the invocation return in the non-tx case is a bit ugly. Really it should be done in UnlockInterceptor, but then the map would have to be a shared object stored in TreeCache. Bleah :(