Разделил бы вопрос на 2 части: критерии выбора и KPI, которые готовы обеспечить.
1) Опыт. И это не срок работы компании. Именно опыт работы сотрудников, кто будет решать ваш проект. Опять же опыт не в годах, а в решенных задачах;
2) Решают ли все ваши задачи. Если у вас несколько задач в рекламной кампании, а агенство все вопросы не тянет - лучше найдите одного подрядчика на кампанию;
3) Комфорт общения и разговор на одном языке. Важно понять, можете ли вы установить контакт с контактным лицом. Вообще, приятно ли Вам общаться с представителем;
4) Есть ли KPI под которые агентство готово подписаться. Если вообще ничего гарантировать не готовы - то смысла с ними завязываться нет.
5) Могут ли назвать KPI по сходным рекламным агентствам: стоимость лида, конверсия по различным источникам и т.д.
Ну и а вообще, есть ли персонал в этом агентстве, или все агентство - это один менеджер со списком потенциальных подрядчиков.