Unless doing a convoluted routing or going via Canada, the OP should forget the notary. A signed letter is generally way more than sufficient for this kind of rather straightforward trip. And if you think these letters become a magic solution just because of a notary on the letter, then I've got some bad news about that too.
CDG gets lots of American kids traveling without their parents and/or with the family name of the child being different than the accompanying adult. It's generally not a problem.