The perm fee is typically paid w/ guarantees. Usually that the candidate stays for 6 months to a year. So you see the recruiter is looking for someone that has dealt with the politics of a large organization, and can be diplomatic and not get himself fired before the refundable portion of the perm fee seasons.
Code, that's the company's problem... The recruiter doesn't care if the guy can actually do the job, they are only matching experience to requirements, and then coaching the CEO on who historically sticks around to take more of the investors $$$..
The problem is not with the recruiters... its with CEO/Founders etc that have no experience hiring people and who aren't good managers to begin with. The best coder may not be the best VP's of engineering.
If you're trying to get a VP job without VP experience well what makes you ready for such a position? What have you done to be entrusted with the heart of a company? You have to show someone that... or make it easy for them to say yes... (that means lower your salary requirements, take more on the backend).. any who
Hope that helps..