From browsing this sub I've learned that Christianity outside of Europe has a much longer history than I thought. Apparently the Church of the East had communities in India, China, and Central Asia, while the Orthodox Church had a major presence in African regions like Ethiopia.
From Western civ classes I've learned that Europeans rationalized their colonization and subjugation of more 'primitive' countries on the grounds that they were spreading Europe's superior civilization, technology, culture, religion, etc. When European missionaries arrived in the colonies on these homogenization missions were they surprised to find centuries-old Christian communities already present? Or did they already know about these distant sects and simply write them off as heretics in need of conversion?
A bit later than what you're looking at, but in "Power, Faith and Fantasy " Michael Oren describes how American Protestant missionaries saw the Orthodox and other Eastern Christians that they encountered throughout the Mediterranean and Middle East as being as badly in need of both secular tutelage and conversion to proper forms of Christianity as the Muslims.
The attitude that Eastern Christians were backwards heretics goes back at least to the time of the Crusades when the need to bring Roman Christianity to the people of the East was the excuse used to sack Constantinople and other realms of the Byzantine Empire.
It also served political purposes to handwave the prior existence of Christianity in prospective colonies. As late as 1898 onwards, support for the US annexation of the Philippines was partly drummed up at home by presenting it as a proselytizing mission to bring the natives from darkness to Christianity, quite ignoring that the Philippines was overwhelmingly Catholic for having been a Spanish colony for over 300 years. This was partly willful ignorance, partly discounting Catholicism as "not really Christianity". Ironically, in the political settlement that the Americans made with the various parts of the archipelago, they mostly agreed with the sultans to not engage in missionary activities in the most emphatically not Christian parts - the Muslim south.
There were a number of cases of these encounters, so I'll focus on the Portuguese in India as an example. There are a group of Christians in Kerala known as Saint Thomas Christians who were part of the Nestorian Church. They were very involved in the spice trade. When the Portuguese first encountered them during the expedition of Vasco da Gama in 1498, they became allies and the Portuguese set up bases and trading posts. A few decades later (in 1536) however, the Portuguese began an inquisition. It started in Portugal and was originally focused on Jews. It was later expanded to include Portugal's colonies. The Saint Thomas Christians under Portuguese control were forced to change their liturgy from the Malabar Rite to the Roman Rite and shift from the Nestorian Church to the Catholic Church.
Source: Frykenberg, Eric (2008). Christianity in India: from Beginnings to the Present. Oxford University Press. ISBN 0-19-826377-5.
Surprised? No. Nestorian Christians and legends about Prester John were very popular in the middle ages - Prester John being a Christian ruler in India (or other countries depending on the legend). The Mongol Horde was rumored to be the army of Prester John, and the fact that Genghis Khan had some Nestorians with him helped.
http://en.wikipedia.org/wiki/Prester_John
When Catholic Missionaries made it out to India and China, they found evidence of old Christian communities, which, no, did not surprise them since the mission of St. Thomas was reputedly to the East. ( http://en.wikipedia.org/wiki/Saint_Thomas_Christians) The country "most suited" to the Christian message, according to St. Francis Xavier ( http://en.wikipedia.org/wiki/Francis_Xavier), however, was Japan. He felt the Japenese ethos, as it were, was a natural match for the message of Christianity, even though they had had no prior exposure to the message, unlike India (where he operated out of) and China.
Most of the replies have been about Byzantine, colonialism, and Nestorian Christians. But was there any formal contact between the major European powers and the emperors of Ethiopia, and was there any account on how the European parties reacted to the seeing a Christian monarch in Africa at the time?