Уважаемая l.kozhevina! Согласно ст.20 ФЗ № 114 "О порядке выезда из Российской Федерации и въезда в Российскую Федерацию", если несовершеннолетний гражданин Российской Федерации выезжает из Российской Федерации без сопровождения, он должен иметь при себе кроме паспорта нотариально оформленное согласие названных лиц на выезд несовершеннолетнего гражданина Российской Федерации с указанием срока выезда и государства (государств), которое (которые) он намерен посетить. 17 декабря 2009 года вступил в силу Приказ Минюста РФ от 19 ноября 2009 г. N 403 "Об утверждении Правил нотариального делопроизводства". Согласно данному документу в согласии на выезд несовершеннолетнего нотариус обязан указывать названия стран, которые несовершеннолетний планирует посетить.
Таким образом, формулировка в согласии Ваших туристов "во все страны мира" противоречит законодательству РФ, т.к.не содержит названия страны въезда.
Что касается возмещения ущерба, то здесь необходимо обратиться к условиям договора. Если доверенность родители  оформляли самостоятельно, без содействия турфирмы, то ответственность за отказ пограничных служб в пересечении границы  турфирма нести не может.