> FYI, I have a pathlib experiment in
> http://hg.python.org/features/pathlib/, with an optional openat-based
> accessor.

Interesting: I used to think that the current API for dealing with paths was a little too basic and terse.

Concerning this issue, one (last) thing: rmtree performs a depth-first traversal of the directory tree, keeping an open FD at each directory level: in case of deeply-nested directory hierarchy, or if there are many open FDs, there's the risk of running out of FDs.
I think the best thing would be to let rmtree fail (provided it closes all the FDs it opened): falling back to the "unsafe" version would be stupid (an attacker would just have to create a deeply-nested hierarchy, and then use the same old symlink race).