I think (or at least hope) that you're misunderstanding the headhunter fees. I'm not aware of any case where a headhunter will charge the candidate a fee, if you run into one who does that's a massive black flag and I'd avoid them like the plague.
It's just a bit of nomenclature. I'm differentiating recruiters from headhunters.
Recruiters behave the way you describe, getting their commissions from the company. Headhunters charge a percentage of the candidate's salary.
Headhunters work at the executive level where jobs are mostly word of mouth. Some candidates are willing to pay them because finding leads can be really difficult at that level.
Most people don't have access to a headhunter because they're not at that level, so I probably didn't need to make the distinction. I just wanted to make sure that the OP didn't pay a fee to get a job since the word headhunter was mentioned.