Before going to a staffing service, I'd maybe consider increasing the posted salary by 50-100% and really making sure the description and requirements is clear.

Odds are, you'll get more quality and not-quality candidates that you can filter out.

You'll already be paying that extra money for any staffing agency (probably with a substantial buyout if you want to permanently hire) so you may as well use that part of the budget to make the job more attractive.