This has been a standard practice in many industries for a very very very long tine... like hundreds of years.
Feel fortunate that it is only just beginning in the airline industry.
(most of the time, headhunters charge the company, but there have always been headhunter agencies that charge the individual in advance, especially when the number of openings is less than the number of applicants)