У меня с обоими дочерьми разные фамилии, выезжаю каждый год и не по разу.
1. Доверенность от второго родителя не нужна, если ребенок едет хотябы с одним из родителей.
2. В ситуации с разными фамилиями - или ребенок должен быть вписан у вас в паспорте или вы должны предъявить свидетельство о рождении ребенка и документы о перемене фамилии - например свидетельство о разводе (т.е доказать что женщина с фамилией Петрова является матерью ребенка с фамилией Иванов).
У меня на прохождение паспортного контроля уходит минут на 5 больше чем у остальных - может это и есть "докопались" ))))

ЗЫ Три недели назад моя старшая выезжала с моей сестрой, т.е. с родной тетей. Доверенность была только от меня. Так по поводу моего ребенка ни одного вопроса не было, пропустили на раз, а вот к родной сестриной дочери "докопались" - т.е. в окошко выкладывается весь комплект документов, т.к. разные фамилии. На прохождение паспортного контроля с двумя детьми ушло минут 10.