Speaking of the Theotokos, when did the Church actually begin to venerate her? It is somewhat strange that her place and date of death is not mentioned even by John who outlived her, considering who she was.
Saint Paul mentions her by name, and although he probably outlived her too, she does not appear as the central figure in the Epistles of the New Testament, with the possible exception of a hint (not by name) in the Revelations.
Obviously, the Apostles and their immediate successors did not consider her even close to the Marian reverence of the Church centuries later. She did not become the subject of post-Resurrection writings even of the people closest to Jesus.
I believe that the Gospel of James speaks in greater detail about her, but then it is not part of the New Testament. It expands on the Gospel of Mark and Matthew and is the earliest text that claims perpetual virginity of Mary as well as the first source known to claim Joseph was a widower -- which of course is not made by any of the four Gospels of the NT.
The consensus is that it was written around 150 AD by someone who claims to be the brother of Jesus (Origen states that he would be His cousin). So, while the entire gospel is rejected along with those of the Gospel of Thomas, the so-called "infancy gospels," the Church uses parts of it (virginity and Joseph being the widower). But this pushes the virginity and sinlessness of the HVM to a century after her death, leaving one to ponder why was her blessedness not obvious from the beginning even to the Apostles, as well as who and where started the Marian devotion?
All good questions, and ones that there can really be no definitive answers to. If one takes a Sola Scriptura approach, then there is no evidence for the veneration of the Theotokos in the Scripture.
It would appear that the obscurity of the origins are due to the fact that this is a part of the inner tradition of the Church, and not a part of the public witness, which is what the Scripture is primarily about. It would have been problematic, to say the least, to emphasize the Theotokos during her lifetime, since this could have detracted from Christ. There was also the Hebrew tradition of women keeping silent -- it was the role of the apostles to preach, and to preach Christ. The tradition of the Church also indicates that the Theotokos, being so physically linked to Christ, who took flesh from her, could do no other than to live a life of unceasing prayer after he ascended to the Heaven. She is, for this reason, seen as the exemplar of monasticism and hesychia.
Flipping it on its head, it is always helpful to ask these questions from the opposite standpoint: i.e. why is there an absence of polemical liturature questioning the veneration of the Theotokos? One would assume that if something new were being introduced into the Church, someone would complain about it, rather loudly. If there is one thing we know about the Church of the first few centuries, it is that they weren't afraid to hash things out to the nth degree if there was the least bit of controversy.
I remember reading an debate between a Reformed Calvinist and a Baptist over the question of infant baptism. The Baptist had to admit that the practice of infant baptism must have begun very, very, early in the history of the Church, since there is no record of any polemical literature questioning the rightness of baptizing infants. He still believed that baptizing infants was wrong, since Scripture didn't teach it, but he had to admit that the practice must have begun at least shortly after the time of the apostles.
I would therefore think that the veneration of the Theotokos would likewise have to have been universal and uncontroversial in the Church within at least a century of the death of the apostles.
Regarding the Protoevangelion of James, I think that it perhaps isn't wise to say, as some do, that our accounts of the conception, birth, entrance, etc... of the Theotokos come from those books. They are part of a collection of books that was handed down within the Gnostic tradition, and the texts themselves should be approached with caution.
What is important to remember about the various Gnostic Gospels and Epistles is that the Gnostics used various techniques to back up their particular views. One technique was to take the "real" New Testament and exise parts they didn't like. Another was to take the "real" New Testament and ascribe Gnostic interpretations to it. Another was to add in passages that suited their fancy. And yet another was to compose entirely new books, and put the names of apostles on them.
Now, it is obvious that the way that these books would be most believable would be if they related stories that everyone knew because of oral tradition -- the Gnostic specifics could then be added onto this. The Gnostics weren't interested in whether Joachim and Anna were old and childless and that an angel appeared to Joachim in the fields. They were interested in their esoteric teachings, and using Christian tradition, particularly tradition that wasn't recorded in the New Testament, was a perfect way for them to trick people into accepting their teachings.
(Note that these techniques are basically the same techniques used by modern textual and higher critics of the Scripture.)
So, one can perhaps learn some historical things of interest from even the Gnostic writings, especially if they are things without doctrinal overtones. They may have been the factual skeleton on which the Gnostics built credibility for their books.
I think that the place to look for authentic teaching on the Theotokos are in the festal homilies of the fathers, and in the services themselves. These reflect the separate, uninterrupted, inner tradition of the Church about the Theotokos.
http://www.maristoz.edu.au/spirituality/sub_tuum.html
We fly to your patronage, 0 holy Mother of God; despise not our prayers in our necessities, but deliver us always from all dangers, O glorious and blessed Virgin.....
In the Coptic Rite of the third century, for instance, the Sub Tuum was part of the liturgical office of Christmas. At the end of that century, Patriarch Theonas of Alexandria built the first real church for local Christians (who prior to that time were accustomed to assemble in homes and cemeteries) and called it the Church of St Mary Virgin and Mother of God. Thus, it is evident that Alexandrian Christians were already calling Mary the "Mother of God" in the third century - long before St Athanasius, who was usually credited with coining the phrase.