Doesn't surprise me. Booking.com has been searching for Perl developers (or people willing to learn Perl) for ages[0], which makes it clear that Perl is important for the company.
At the same time, I suspect not many developers have an interest in learning Perl or working with Perl on a day to day basis. Booking.com seems to have a hard time finding said Perl devs.
But they want you to relocate. That's why they're having problems finding a developer. How many people want to leave their country/city/family/friends for a job?
I'm sure they would find quite many candidates if they were willing to offer premium compensation.
When there is a talk about shortage of skilled workers, it is really about shortage of skilled workers willing to work for average or below-average compensation.
At the same time, I suspect not many developers have an interest in learning Perl or working with Perl on a day to day basis. Booking.com seems to have a hard time finding said Perl devs.
[0]: http://careers.stackoverflow.com/jobs?searchTerm=booking.com...