> So, two interesting questions: does this in fact match the behavior of 
> os._execvpe, and does it match the behavior of the shell? 

I think it's fine. child_exec() tries all paths. It saves the first error that's not ENOENT or ENOTDIR. The saved error gets reported back, else ENOENT or ENOTDIR. This is the same as os._execvpe:

    for dir in path_list:
        fullname = path.join(dir, file)
        try:
            exec_func(fullname, *argrest)
        except (FileNotFoundError, NotADirectoryError) as e:
            last_exc = e
        except OSError as e:
            last_exc = e
            if saved_exc is None:
                saved_exc = e
    if saved_exc is not None:
        raise saved_exc
    raise last_exc

Perhaps the rule for PATH search errors should be documented for os.execvp[e] and subprocess.

I think it matches the shell, except, AFAIK, the shell doesn't distinguish ENOENT and ENOTDIR errors. For example, where "/noexec" is a directory that has no execute access:

    $ /bin/sh -c spam
    /bin/sh: 1: spam: not found

    $ PATH=/noexec:$PATH /bin/sh -c spam
    /bin/sh: 1: spam: Permission denied