To put this agreement in perspective, this recruiter has reduced their direct financial incentive to match you to the right company.
For a $80,000 a year job, they're looking at $16,000 for placing you. If they charge you 20% of that if you don't work out, that's $3200. If they spend 40 hours placing you, that's not a bad yearly income - if they just shotgun your resume, they can make real money.
And if the salary, fee, and your percentage are significantly higher, they can make really good money.
Even if it was legal, I would run as fast as I could in the other direction. Think of it this way: what happens if you start the job and come to find out the company is into some shady business and you wanted to quit?
One thing I neglected to mention to this recruiter: I free-lance as an expert witness in computer forensics cases. I've done this for a labor lawyer in the state where this firm operates. I will forward this "agreement" to the lawyer.