Все подобные посреднеческие фирмочки работают примерно так.

• Мы обещаем помочь заполнить формы
• Мы обещаем поделится сокровенными знаниями о возможных граблях
• Мы может быть даже составим какой-нибудь запрос куда-нибудь
• Мы аккуратно собираем деньги с соискателя (хорошо если поэтапно), но СОВСЕМ не несем никакой ответственности и не даем никаких гарантий, поэтому реальная польза которую мы может оказать полностью зависит от нашей доброй воли.
• Даже если мы (в лице нерадивого сотрудника) совсем забъем болт на ваш случай, мы теряем только недополученную прибыль со следующих этапов.
• Это ВАША задача найти работодателя и предоставить все необходимые справки, а мы так уж и быть перешлем их по почте или курьером (за ваш счет)

И где вы видите здесь мошенничество. И какая вам разница как у них дела с лицензией.

Это взаимоотношение фирмы и государства. То бишь отстегнула фирма крыше или нет. Конечно если фирма кинула даже крышу, то с вами и подавно церемонится не будут. Поиск или нахождение. И не сводится ли поиск к забиванию вашей анкеты на одном, двух сайтов и не шмагла я.

Формально, они мошенничества не совершают - оказывают консультационные услуги, вам правда от этого не легче.
Сильно напоминает известную аферу, когда аферист собирает с абитуры деньги на взятку для поступления. Тем, кто не поступил возвращает, а тем, кто поступил сам, стало быть не возвращает. Все расходы - на создания важного вида и запугивания клиентуры.