Wow that is really interesting, how did you manage to sell them a paid (hourly) service when as you said they had firms knocking down their door doing it on contingency?
Not the OP, but commission-based recruiting seems to incentivise the wrong kind of recruiting, i.e. "find someone we can shove down their throat". I would personally rather pay an experienced recruiter by the hour, even if it meant fewer (hopefully higher quality) leads.
And that was basically the pitch... "We aren't magic, we just do what you would do. If you have the tim to recruit yourself, do it. If not, give us a try, and if it's not working, fire us."