Are another user's non-empty subdirectories safe from deletion in my directory?
One can only remove a directory (with the rmdir() system call) if it's empty.
rm -r dir removes the directory and all the files in it, starting with the leaves of the directory tree and walking its way up to the root (dir).
To remove a file (with rmdir() for directories and unlink() for other types of files, or *at() variants), what matters it not the permission of the file itself but those of the directory you're removing the file from (beware the t bit in the permissions, like for /tmp, adds further complications to that).
Before all, you're not really removing the file, you're unlinking it from a directory (and when it's the last link that you're removing, the file ends up being deleted as a consequence), that is, you're modifying the directory, so you need modifying (write) permissions to that directory.
The reason you can't remove non-empty-dir is that you can't unlink subdir from it first, as you don't have the right to modify non-empty-dir. You would have the right to unlink non-empty-dir from your home directory as you have write/modification permission to that one, only you can't remove a directory that is not empty.
In your case, as noted by @PeterCordes in comments, the rmdir() system call fails with a ENOTEMPTY (Directory not empty) error code, but since you don't have read permission to the directory, rm cannot even find out which files and directories (including subdir) it would need to unlink from it to be able to empty it (not that it could unlink them if it knew, as it doesn't have write permissions).
You can also get into situations where rm could remove a directory if only it could find out which files are in it, like in the case of a write-only directory:
$ mkdir dir
$ touch dir/file
$ chmod a=,u=wx dir
$ ls -ld dir
d-wx------ 2 me me 4096 Nov 30 19:43 dir/
$ rm -rf dir
rm: cannot remove 'dir': Permission denied
Still, I am able to remove it as I happen to know it only contains one file file:
$ rm dir/file
$ rmdir dir
$
Also note that with modern Unices you could rename that non-empty-dir, but on some like Linux or FreeBSD (but not Solaris), not move it to a different directory, even if you also had write permission to that directory, as (I think and for Linux, as suggested by the comment for the relevant code) doing so would involve modifying non-empty-dir (the .. entry in it would point to a different directory).
One could argue that removing your empty-dir also involves removing the .. and . entries in it, so modifying it, but still, the system lets you do that.
Ignoring the potential change through the ACLs, I can confirm this behaviour for my system (without ACLs).
The observed behaviour is the logical consequence of two principles:
1) The rights for a directory determine who can change the directory, i.e. delete entries in the directory. The rights of the entries in that directory play no role in this.
2) Removing a file potentially requires removing and cleaning up associated imformation, i.e. inodes, block allocation lists etc. That's why you can't remove a non-empty subdirecty without having cleaned up all files it contains, because otherwise the files it contains would become inaccessible, but there associated information would not have been cleaned up.
So you can remove empty-subdir, because you have the rights to write to the directory it is in. You can't remove non-empty-subdir, because you don't have the rights to clean up the files that are contained in this subdir first.
There's really no rationale or use case for this. One could have built recursive clean up of a subdirectory into the kernel, but the original Unix kept everything simple, and recursive clean-up would have been too complicated when it can be achieved with a user-space utility.
I can't provide a comprehensive overview between different flavours, but this was the behaviour in the original Unix, and I would expect it to be the same in every flavour of Unix, and I'd be surprised if there was a flavour of Unix that behaved differently.
I tried to reproduce what you describe, and ran strace rm -rf ./nonempty. What that reveals is the following:
unlinkat(4, "subdir", AT_REMOVEDIR) = -1 EACCES (Permission denied)
and according to unlinkat manual ( which on Linux is same as unlink(2), emphasis added by me):
EACCES Write access to the directory containing pathname is not allowed for the process's effective UID, or one of the directories in pathname did not allow search permission. (See also path_resolution(7).)
Since the parent directory, nonempty, doesn't grant user x (search) permission, it makes sense based on the EACCES description that subdir can't be removed.