Frankly, I doubt I could code my way out of a paper bag without access to the Perl docs, books, mailing lists, etc. that I normally use to attack problems. It's like taking an experienced magazine editor and saying "if you're such a great editor, write me a poem." Creating an artificial environment that's completely unlike the one I expect a candidate to work in just doesn't seem very useful to me.
I also don't agree that it's easy to walk-through and explain someone else's good code. Maybe you need to ask more interesting questions. "Why did you choose to do the POD with these headings?" "What was your approach to testing this method?" "Have you considered using some alternative module on CPAN?"
I doubt a person who lied about their code sample would be able to demonstrate competent understanding of it to my satisfaction, especially when paired with questions about source control, project tracking, and involvement with the Perl community. Meanwhile, I save myself time by filtering out the candidates whose code samples don't demonstrate the skills to merit an interview.
Regarding the problem you speak of with finding good people, it will always be a candidates' market for the best developers, because they are by definition in limited supply. You can hire people who are not as good, or you can provide something (e.g. higher pay, Google-esque perks, a worthy cause, the freedom to telecommute) that makes the best developers want to work for you rather than someone else. Of course you need to get the word out as well, and you can do this in a variety of ways (networking and sponsorship at Perl conferences, local PerlMongers events, participation on mailing lists, etc.).