кто потребовал на выезде с Украины какое-бы то ни было разрешение для гражданина РФ? Они с тем же успехом могли у Вас разрешение от соседей и заведующей детским садом потребовать. Если все документы в порядке (оригинал СоР и штамп/вкладыш о гражданстве) то требование не законно и они об этом прекрасно знают