Extend the idea of "lemon laws" to hiring. Every new hire has a 3 month try-out period (as a contractor?) where they will be fired if it doesn't work out. If you make this point forcefully during the interview, some low-quality applicants will seek safety elsewhere rather than risk losing their job, while high quality applicants won't be deterred.
http://en.wikipedia.org/wiki/The_Market_for_Lemons
Solve that problem to solve this one.