Perhaps a reputation system for recruiters, i.e., an Angie's List for recruiters, could help here? That could be a useful service.

Its a tough market to serve because the most people don't change jobs more than a couple times in their career.