This question's been tough for me recently. Why is there so little evidence of the practice for at least around 350 years of the Church's history? Is there something I'm missing? Are there historical records of the practice by any Church historians or theologians or liturgies or anything?
Your dating is mistaken; there is plenty of very early evidence, some of it very weighty in significance.
Here is one important example already in Christmas Liturgy c. AD 250 (mentioned in the Energetic Procession link, but here is more detail).
“Beneath Thy Compassion”: Earliest known prayer to the Theotokos: "Under your mercy we take refuge, Theotokos! Do not despise our petitions in tribulation, but rescue us from danger, Only Pure, Only Blessed One."
Extant Coptic ms. dates paleographical circa 250 AD (E. Lobel); liturgical content -unlikely to represent a sudden revolution of praxis. Coptic context was the Christmas Vespers service.
Multiple ancient versions of the prayer Coptic, Greek, Syriac, Armenian and Latin -wide geographical distribution / acceptance. Still used in Eastern Orthodox and Roman Catholic Churches (e.g. http://youtu.be/cj6lNLVBbBg
Acquired by the John Rylands Library (University of Manchester) in 1917 (cf. Catalogue of the Greek and Latin Papyri in the John Rylands Library, III, Theological and literacy Texts, Manchester 1938, pp. 46-47; John Rylands Papyrus #470).
Context of origin in persecution.
"Theotokos" in liturgical context two hundred years before the controversy linked to Nestorius and resolved in 431AD by the Ecumenical Council of Ephesus. The term is also attested at the same date in a letter from Bishop Dionysius to Paul of Samosata. Origen is said to have used the term in his commentary on Romans by the early historian Socrates (Hist. Eccl. VII, 32 – PG 67, 812 B). This commentary, unfortunately, is now lost.
Perpetual Virginity (cf. the Epiphanian view still traditionally held in Eastern Orthodoxy represented in the Protevangelium of James, the Gospel of Peter and the Infancy Gospel of Thomas, probably all from second-century Syria).
As has been mentioned too there is a great deal of earlier epigraphical data which attests Christian prayers to the dead, e.g. Cemetery of Callisto "Live in eternal peace and pray for us"), Cemetery of Domitilla (multiple examples asking for intercession for the living left behind), Cemetery of the Giordani on the Via Latina, etc. e.g. IANVARIA BENE REFRIGERA ET ROGA PRO NOS [sic]: " Januaria, be refreshed, and pray for us!" http://www.archive.org/stream/christianepigrap00maruuoft/christianepigrap00maruuoft_djvu.txt
Similar praxis is also bountifully attested in Jewish context before Christ (cf. 2 Mac. 12, 43-46 and https://faculty.biu.ac.il/~testsm/Angels_Intermed.html
The early and universal doctrine of the Communion (koinonia/fellowship -Bonhoeffer translated the word "life together") of the Saints is found in very early creeds: the Apostle's Creed and its precursor, the Roman Creed. It is attested in tomb inscriptions in the catacombs and early liturgy in multiple geographical regions. This understanding passes through to Christianity from Judaism and is attested in the Deuterocanon and extra-canonical early Christian literature and letters. These are but selective examples (see others in the link from Energetic Procession in a previous post). From the beginning Christians have understood the Church to be a single living body: visible, invisible, and indivisible -all three. Not even death can separate us from Christ's body. Christ said "I am the resurrection and the life. Whoever believes in me, though he die, yet shall he live, and everyone who lives and believes in me shall never die. Do you believe this?" -John 11:25-26 "Within the Mystical Body there takes place a unique communication and correlation: within that communion the gifts of the Holy Spirit -the power to forgive sins, to transmit salvation, to suffer by proxy for one another, and the power of intercession- become effective. And these powers extend down to the domain of the dead, for God is "a Lord of the living, not the dead." -Ernst Benz, The Eastern Orthodox Church: Its Thought and Life.
If nothing else these examples should suffice to alert you to the need to revise your figure of 350 AD -not sure how you derived that date!