Согласие на временный выезд без сопровождения нужно. Оформляется у любого нотариуса, от обоих родителей. Либо одна бумажка от обоих родителей, либо каждый родитель оформляет согласие самостоятельно. Но согласие вместе с оригиналом свидетельства о рождении (даже если ребенку уже есть 14 и у него есть паспорт) не аэрофлоту нужно, а пограничникам российским, поэтому "дальнейшие звонки и поездка в офис ясности не внесла".