I think you're mixing two concepts: relative paths (which are allowed after #! but not very useful at all) and file lookup through $PATH (which is not done by the kernel, maybe it's some shell trickery).
> and file lookup through $PATH (which is not done by the kernel, maybe it's some shell trickery)
It's libc. Specifically, system(3) and APIs like execvp(3) will search $PATH for the file specified before passing that to execve(2) (which is the only kernel syscall; all the other exec*() stuff is in libc).
I think you're mixing two concepts: relative paths (which are allowed after #! but not very useful at all) and file lookup through $PATH (which is not done by the kernel, maybe it's some shell trickery).