По мнению Dresdner при пересечении границы пограничник будет проводить допрос сопровождающего гражданина Украины с пристрастием на предмет того, не является ли ребенок его сыном/дочерью. При получении утвердительного ответа пограничник тыкнет ему ст. 7 Закона Украины "Про громадянство України", а затем откажет в пересечении границы согласно ст.2 ЗУ "Про порядок виїзду з України і в'їзду в Україну громадян України".
При этом - по моему мнению - это явное превышение полномочий пограничника так как:
1. Установление наличия гражданства является компетенцией определенных органов, согласно ЗУ Про гражданство. Пограничники в него не входят.
2. Даже при обращении в эти органы - если ребенок не оформлялся гражданином Украины - то ответ будет негативный.
3. Согласно ЗУ Украины про гражданство - ребенок может не иметь гражданство Украины, даже если его родитель его имеет. На это могут быть разные причины. Например, если ребенок вышег из ГУ вместе с одним из родителей или родитель получил ГУ после рождения ребенка.
ПС. Насчет спора, когда у украинского ребенка появляется гражданство Украины. - Спору нет - с рождения. Но есть такой процесс, который назвается "Оформление получения гражданства по рождению" и этот процесс - ручной - т.е. надо писать заявление и т.д. До этого момента гражданство - есть, но оно не оформлено.
ППС. efes pilsener

Украинские законы лучше всего смотреть тут: http://zakon4.rada.gov.ua/laws/show/2235-14/page