Having said that, other non-printing characters is definitely a possibility, I ran into this type of problem just a couple of days ago under VMS: for some reason, my Windows editor added some presumably utf-8 character at the very beginning of my program, which refused to even compile.

And, thinking back to my initial reaction in my first sentence above, it is absolutely true that if the shebang line is faulty, well, it is not interpreted by Perl but by the shell. And the shell is not as clever as Perl. But then, maybe I should have met the problem with DOS formated Perl script? Well, probably not, because I actually almost never really use the shebang line, my Unix shell scripts running Perl programs almost always launch the Perl program with a command such as perl my_script.pl (this way I don't run into RWE problems if I forgot to change privileges). And the same when I run a Perl program directly from the shell prompt. So that, in the end, your hypothesis might very well be right.

Well, all this to say that I initially thought you were probably wrong, and that, after a second thought, I think you might be right.

Perl can handle the DOS line endings just fine, but as you said, it's the shell that can't (it tries to find a program named /usr/bin/perl^M to pass the script to). The cases you had where you didn't have issues with DOS line endings could have been that your #! line was something like: #!/usr/bin/perl -w^M, in which case the shell can find /usr/bin/perl and passes it the command line argument -w^M along with the script name, and perl can process those fine.