Recruiter here (independent agency), and I've always felt that the problem is that fees are too high. With this much money being thrown at recruiters, it keeps the bad ones in the business. If fees were lower, only the best recruiters would survive - as well as those that are just best at making money, which doesn't necessarily mean 'best' - and eventually most of the bottom recruiters would exit the market.
Contingency recruiting is the overall source of the problem. Someone could make a few lucky hits a year and make good enough money to stay in business. If fees were say half of what they are now, that would put many out of business, and I'd assume those would the recruiters that everyone complains about.
The size of fees also leads to the ethics problems. You may or may not lie for $5, but what kind of lies might you tell for say $30,000? The large numbers and competitive nature make it a high-reward game that gives incentive to cheat and lie when necessary.
Smaller fees. I use small flat fees with a portion paid up front. The fees are small enough that I have little incentive to lie, and the up front portion is small enough that I'm going to hustle to get the second payment.
Contingency recruiters absorb 100% of the risk, meaning they can work hundreds of hours on a search but if the recruiter down the street fills it they get nothing. This is the reason fees are high - the risk factor. If you remove that risk to some degree (or share the risk) by paying some money up front, recruiters should agree to lower fees and companies should like the results.
As a recruiter, would I rather compete against 20 bigger firms for a 30K fee or would I rather be practically guaranteed a 15K fee? The answer for me is the latter, but may differ for others.