In both cases -- according to ktrace(1) on FreeBSD 6-STABLE with Perl 5.8.8 in zsh 4 -- perl is complaining, through execve(2), about the missing interpreter not the file itself being executed.

Corion's reply reminded me that I just had added '.' to the path; thanks. It turns out the message, or rather error from execve(2), is the same whether the problem is not finding the file being executed, or if found, with missing interpreter listed in the file. Anyawy, what OP said.