Выехать из России да, мы можем свободно, но вот въезжаем в Украину мы уже по их законам и наши законы их не волнуют.
их законы распространяются только на граждан их страны. на граждан РФ они не распространяются. если Ваши дети имеют российское гражданство, требовать согласие второго родителя украинские погранцы не имеют права. а вот если Ваши дети имеют украинское гражданство - тогда да, без согласия не выпустят и не впустят)
я тоже каждый год, иногда не раз, на Украину с детьми езжу. никто к нам не прикапывается
правда на данный момент, в связи с ситуацией на Украине, я не в курсе, может с нашей, российской, стороны тоже изменились законы

надо уточнить. но в прошлое лето согласие второго родителя точно не требовали.