I would try and get a recommendation from someone on a recruiting firm they used and liked. When I was looking, I got references from a few friends on companies they used and specific recruiters used. This way, you already have a little background on the company and you know the person is probably going to be helpful.
I'd be careful using the huge agencies. A lot of them just have tons of recruiters who are just worrying about getting a ton of resumes and will not give you the time and effort. I have also heard stories that some of these large places will just start sending your resume out everywhere, without even asking you if you are interesting in the job.
Bottom line, try and get a reference from someone that has used a recruiter they liked. Thats what I did and I ended up with a great recruiter who I talk to on a regular basis.