`os.rmdir` not working on empty directories?

Question

Assume the following directory structure:

A
+-- B
|   +-- C
|   |   +-- D
|   |   |   +-- E

where no directory contains any files (not even invisible ones). Running

os.rmdir("A/B/C/D/E"); os.rmdir("A/B/C/D"); os.rmdir("A/B/C"); os.rmdir("A/B"); os.rmdir("A")

in Python (3.5) yields

OSError: [WinError 145] The directory is not empty: '##'

where ## is either A, B, C or D, but executing each function manually does not produce this exception. I'm aware that there is shutil.rmtree, but the documentation of os.rmdir clearly states

Remove (delete) the directory path. Only works when the directory is empty, otherwise, OSError is raised. In order to remove whole directory trees, shutil.rmtree() can be used.

which doesn't seem to be the case, at least on Windows systems. The only workaround I found so far (excluding shutil.rmtree) is

def rm (dir_path):
    while len(os.listdir(dir_path)) > 0:
        pass # Maybe include timeout here to not lock the program
    os.rmdir(dir_path)

Is this a bug or is os.rmdir supposed to not block until the directory is removed?

EDIT: Looking at the source of os.rmdir (for CPython 3.5 on Windows) we can see that RemoveDirectoryW is used for deletion. The remarks section of the documentation of RemoveDirectoryW states

The RemoveDirectory function marks a directory for deletion on close. Therefore, the directory is not removed until the last handle to the directory is closed.

Even though I tried to make sure that there is no handle to the directory, I think this might actually be the problem (thanks to @armatita for the hint).