In the original BSD Unix, and current versions of Linux, the shebang is not implemented by the shell, but by the execve system call. When the file that's handed to execve is not a binary executable (as found from its magic number), then the call checks whether the first two characters are #!. If so, it attempts to exec the file named immediately afterwards instead, passing it the original file as input. The path to the file has to be valid -- there is no search of $PATH, which is maintained by the shells, not at the kernel level. Hence, your example of #!perl would work only when the Perl executable was in the current directory of the process that was calling exec.

What can add to the confusion is that Perl will actually examine a shebang-looking line to see if it should "fake" a shebang, for systems that either don't implement it (Win32 comes to mind), or which have a crippled version that doesn't allow passing arguments. You can get much more detail on this behavior in the opening paragraphs of perlman:perlrun. The /usr/bin/env perl trick is described there as well.

HTH