From my UK experience - I would take the time and get the right type of person and train them in the way you want. Its less trouble than getting the wrong person and having them screw it up or getting someone with the right skills but wrong attitude for your company
Paying well helps, having a great environment helps
Get out and give kick ass SEO presentations at conferences and let people know you are hiring - being known as an leader in an area can help attract ambitious people
Maybe ask your current staff? Good people tend to know other good people
Getting out and meeting people is the best way I know - network at SEO events and see who you gel with
Once you have someone great, make sure you keep them - set them decent long term challenges and maybe think about business related remuneration like shares etc
Reversing the problem, some alternate thoughts:
- slow down growth until you get the right people on board
- cutback on the trouble clients and keep the good ones
- only grow the stuff you can scale (linkbuilding over consultancy)
- bring new clients on board only at a higher rate
Let me know how it goes, Id love a solution to this problem!
Stephen