Picking an agency has been one of the toughest things I've ever done! Screen them, screen them, and then screen them again!
I joined 3 different lists that I could ask opinions of others about different agencies. I narrowed it down to 3 or 4 that I had heard good things about and then posted them on here asking for info on them through private message (we're not allowed to discuss agency information on this forum in public). I took those few and did better business bureau checks and checked their agency license. I asked the agencies a ton of questions and went with the one that fit us and our situation best.
This took me 2 months and if we weren't under a deadline, I probably would have researched at least another 2 or 3 months. I'm VERY happy with my choice though.
It was worth it!