I'm lazy, so when this happens to me I just add a -w to the shebang line:

#!/usr/bin/perl -w

The -w option seems perfectly happy to have a ^M after it. It's not really safe, but for the most part carriage returns won't make any difference at the ends of lines; they're just whitespace to perl anyway.

Of course, it could make the bugs even more mysterious...