No ethical headhunter would make a deal like this. Recruiting costs should be the responsibility of the employer, with the implicit understanding that not all employees will stick around (especially if they're abused), and the employer bears that risk.
You might want to consult a lawyer to find out if this kind of contract is legal or enforceable in your state.
I'm not a lawyer and can't give you legal advice, but I'm almost 100% sure that what you're describing is illegal. Many lawyers will do a free consult to make sure that the case is worth taking, and you can take advantage of that to feel this out.
That is not a bad idea actually. As long as we got a package or something. We moved to this small city in the hopes of joining this amazing startup working with amazing technology. The downside of leaving is multifold:
1. Headhunter wants his commission back
2. We are in a small city, so interviewing is difficult, may not be able to get a job until i move to a normal city like SF or Austin or NY and start interviewing/networking on the ground.
3. We moved to this new city, need to wait until June when schoolyear is over.
You might want to consult a lawyer to find out if this kind of contract is legal or enforceable in your state.