The headhunter I used charged 2 weeks pay to be payed out of earnings over a few month time period. I figured it was better to pay and get a job (and a temporarily reduced paycheck) than to keep looking for a month or two (with no paycheck).
I used a headhunter when I was new to the business and needed a job.