Насколько легальны сервисы обратного звонка?

В нашей стране контроллирующие органы не интересует наличие лицензий до тех пор пока не причинен ущерб.
Можно водкой торговать из под полы, пока кто-то не капнет в органы, никто не засуетится.

Не знаю как в вашем случае, но в начале века (15 лет назад) для выхода в интернет население использовало dial up соединения . Телефонная связь часто тарифицировалась по "повременке" ( по типу рубль в минуту). И чтобы любители подолгу зависать на телефонных модемах в интернете не страдали финансово, на модемах оператора настраивали callback (обратный прозвон юзеру), при котором тарификации не было (ибо шел для пользователя входящий звонок).
Были юрлица (не операторы связи), которые (купив модемный пул, интернет канал, и выход в телефонную сеть ) выпускали карточки для выхода в интернет по данной схеме и прикрывались они агентскими договорами с оператором связи + у них было сертифицированное оборудование, размещенное на узлах связи, которые были сданы и приняты РосСвязьНадзором. Все законно. Думаю и сейчас аналогично.

Не все возмездные услуги требуют лицензии. Список услуг конечен и содержится в нормативных актах. Если Вам будут выставлять за минуты телефонного соединения - лицензия. Если будет написана услуга обратного вызова или аренда ПО (АТС) для осуществления обратного вызова - то лицензия не требуется.
То есть варианта обхода лицензии есть два:
1. Оказывать услугу подпадающую под лицензию бесплатно, а брать деньги за другое.
2. Назвать услугу так, что бы она не попала в перечень лицензируемых.

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