I've intended for this post to be a placeholder until I publish my next entry on the linguistic history of the Arabic language until the early Islamic period. I've adapted it from a post I made elsewhere. It represents an early phase in my research on the religions in pre-Islamic Arabia, it's rather informal but so is the nature of my research right now. InshaAllah it'll be added to, corrected, and fixed as time progresses.
The presence of Christianity in Arabia was already centuries old by the time the Prophet was born. Historical Arabia was identified as a region spanning from the Eastern banks of the Nile to the Euphrates and as far north as the Syrian desert. According the Socrates Scholasticus, the Byzantine ecclesiastical historian, not the Athenian philosopher, a Queen Mavia (ماوية) of the Ishmaelites, who reigned from the late fourth century to the early fifth century, converted to Christianity. She went on to appoint a Bishop named Moses, another "Saracen" (Arab) who led a monastic life and was reputed to preform miracles. Eusebius writes about an Arab Monarchian named Beryllus, Bishop of Bostra. He believed that Christ was a distinct divinity but only possessed the Divine nature of God the Father after the incarnation. Origen of Alexandria converted him back to "orthodoxy" (in the lower-case sense of the word, not upper-case sense referring to the Orthodox Churches).
It seems that by the birth of Prophet Muhammad there was a major presence of various "heretical" Christian groups. A misattributed dictum of St. Theodoret of Cyrrhus states that "Arabia hæresium ferax", "Arabia is the bearer of heresies". Scholars have attempt to identify the groups present in Arabia using antique and mediaeval sources and the Qur'anic description of their doctrines.
Theophilos Indus, an Arian Bishop sent by Emperor Constantius II to Asia via Arabia as a missionary. He is reported to have converted the people of Himyar to Arianism. He was Heteroousian, a follower of the theologian Aetius, who denied that Christ and God the Father were of the same substance. It's possible that Arianism survived in the region.
There was also a presence of Severan Monophysites, followers of Severus of Antioch who believed in the "natural union" of Christ's two natures, concentrated on the Red Sea coast (Hijaz and Yemen). The Julianists, a group closely related to the Docetists, are of particular interest due to their rejection of Christ having died on the cross -- a view also found in the Gnostic Apocalypse of Peter (where Christ is in a tree and laughing at whoever is being crucified). Irfan Shahid states Ashab al-Ukhdud (People of the Ditch) that the Qur'an mentions were Monophysites. Their account is also mentioned in text called "The Book of the Himyarites", a Syriac work which was translated into English by Axel Moberg. Their leader was St. Arethas (Harith) was written about in the 7th century text Acta Sancti Arethæ/Martyrium Sancti Arethæ.
There was also a Nestorian presence in Arabia. The Prophet was aware of this and the Qur'an even employs the Nestorian idea of "Isa b. Maryam" to deny that Christ is the Son of God. The aforementioned Book of the Himyarites also has a passage were Dhu-Nuwas employs Nestorian terms to refer to the Christology of the "majority of Christians" (in his realm).
Though Monophysitism did become dominate after the fall of Dhu-Nuwas, Nesotrianism returned with the conquest of South Arabia by the Sassanids. In the lifetime of the Prophet, Nestorian missionaries from Najran would go to Ukadh to preach, and Prophet Muhammad encountered one who left an impression on him, Quss b. Sa'idah al-Iyyadi. He was possibly a bishop of Najran. Irfan Shahid mentions this as a matter of fact in "Islam and Oriens Christianus". However, he's also argued against this position in his entry on Quss b. Sa'idah in the Brill Encyclopaedia of Islam, saying that it was just a conflation of several facts about him and the Episcopate of Najran.
Shahid believes there also might have been an Ethiopic Christian presence. This is based on what seems to be Ge'ez terms being used by the Qur'an, such as Nasara rather than Masihiyyun, Isa rather than Yasu'. Though in the case of the latter Arthur Jeffery demonstrates how this could have also happened as a result of natural linguistic corruption when the word transferred from Syriac to Arabic.
References and Further reading:
Irfan Shahid's article "ISLAM AND ORIENS CHRISTIANUS: MAKKA 610-622 AD" represents a bulk of the research here, I would highly recommend it. You might also want to check out Irfan Shahid's series on Byzantium and Arabia. Gabriel Said Reynold's The Qur'an in its Historical Context (both parts one and two) might also prove useful. And Darren M. Slade's article "ARABIA HAERESIUM FERAX (ARABIA BEARER OF HERESIES): Schismatic Christianity’s Potential Influence on Muhammad and the Qur’an ".