I discussed with Jay Yin on IRC and we understood the issue on his setup: the last entry of his PATH environment variable is a path to an existing *file*, not a directory.

In this case, subprocess.Popen() fails with ENOTDIR if the program cannot be found in any other directory of the PATH.

Copy of _posixmodule.c:
---
    /* This loop matches the Lib/os.py _execvpe()'s PATH search when */
    /* given the executable_list generated by Lib/subprocess.py.     */
    saved_errno = 0;
    for (i = 0; exec_array[i] != NULL; ++i) {
        const char *executable = exec_array[i];
        if (envp) {
            execve(executable, argv, envp);
        } else {
            execv(executable, argv);
        }
        if (errno != ENOENT && errno != ENOTDIR && saved_errno == 0) {
            saved_errno = errno;
        }
    }
    /* Report the first exec error, not the last. */
    if (saved_errno)
        errno = saved_errno;
---

If the first execv() calls with ENOENT and the last one fails with ENOTDIR, the function fails with ENOTDIR.