I called the Embajada here in Canada for an "official" word, and they said that if the parents have shared custody, then the accompanying parent must have a notarized letter of authorization from the other parent but it does not need to be "legalized" by them prior to travel. (Hollywud, maybe you could update this requirement on Debbie's site?)
As Hillbilly suggested, I will also take my divorce papers showing custody arrangements and my daughter's detailed birth certificate together with the notarized letter and her passport. I'd be more relaxed if I was better versed at handling bribes, should I need to offer one, or if I knew that my 10 year old wouldn't have a stroke if we were called off to the side for any reason! lol
If anyone needs a sample letter for a Canadian, I have one, just PM me.