I work at a bank, and we need Perl programmers too. We can afford to pay a lot better than booking.com, but we can't find anyone, either. It's very odd. (And it's not just Perl, we had the same problem with Java and C#, and are having the same problem with C++. Might as well rewrite our app in Haskell... at least those languages have a community.)
The other thing that I see as being difficult for booking.com is that people don't want to work with 40+ other people. Between learning "the rules" from the people already there and teaching the new folks how to program, there is never any time to get anything done. (My second "real job" was like this; I was not even a "team lead" and yet all I did was teach other people basic Perl + Database stuff. We got exactly no work done. At least if I was by myself I would have been able to do one person's work.)
In fact, I find the other Perl team in my office to be too big -- and they only have 4 people!
Check that your candidates know how to develop software, make sure they are comfortable with functional programming so they don't break anything, and give them a couple books (programming perl & higher order perl) to read for a week after joining.
For instance, my webby experience with Perl is CGI::Fast, POE::Componenet::FastGI, Plack::Request with my own dispatcher, DBI itself. Where often the places are looking for Catylist or mod_perl with DBIx::Class / ORM, and I feel uncomfortable applying for a positon where my current skill set doesn't meet the technologies they use even if I could pick up either quickly.
In general my non-webby Perl experience is sufficient.
Does anyone else run into this, and if so how do you handle it?
It's a little odd if you know OO Perl but don't use Moose, but not a deal-killer. Honestly, I've found that there is a large faction of Perl programmers that refuse to leave the 1990s behind, and those are the people I don't want to hire. If you just don't know something but are willing to learn, then that's perfect. It's the "I will absolutely not use Moose" that == unemployment :)
Half the jobs I've taken give deadlines for projects that make it impossible for me to learn more than I know to complete them and the list of things I have to learn in my time (that also competes with lists of projects, blog articles and other things) is growing constantly. I miss having free time.
I'm thinking about a couple of months vacation after this job, to do some web hacking and learning the newer frameworks.
I really like the present place, but I almost doesn't touch the web/CPAN. I have managed to drag people here from 1999 to 2005 or so, but that is probably the limit. :-(
(The killer now, is that I seem to be in the worst place in Scandinavia to have a peanut allergy. [Edit: The lack of challenge to learn new things is not good either.])
The few Perl dev jobs I've interviewed for and taken have relied on unbelievably basic programming tests.
You also mention location specificity -- this hurts employees and employers. Employees don't want to relocate, and employers don't want the communication barrier that telecommuting raises. (And FWIW, having telecommuted at an all-telecommute company... it kind of sucks on both ends.)