when CreateDirectory returns ERROR_ACCESS_DENIED and “shouldn't”

You're dead right. The documentation doesn't even list ERROR_ACCESS_DENIED as a possible error code for that function so it may well be a bug.

I would do as you suggest in implementing a retry/backoff strategy.

In other words, if you get that error, try again up to three times with no delay (obviously stop at any point here if you get a non-error return code), then up to four more times with delays of (for example, 100 milliseconds, 500 milliseconds, 1 second and 2 seconds).

This sort of strategy (which I've used before) usually gets around any temporary resource shortages. If you still can't create the directory after 7 attempts and 3.6+ seconds, you can probably safely assume it's not going to happen.

Your function could be as ugly as (pseudo-code):

def createMyDir (dirname):
    if createDir (dirName) return true;
    if createDir (dirName) return true;
    if createDir (dirName) return true;
    sleep (100)
    if createDir (dirName) return true;
    sleep (500)
    if createDir (dirName) return true;
    sleep (1000)
    if createDir (dirName) return true;
    sleep (2000)
    return createDir (dirName);

but you may want you make it a little more elegant:

def createMyDir (dirname):
    delay = pointer to array [0, 0, 0, 100, 500, 1000, 2000, -1]
    okay = createDir (dirName)
    while not okay and [delay] not -1:
        if [delay] not 0:
            sleep ([delay])
        delay = next delay
        okay = createDir (dirName)
    return okay