In 1.13 we have the fantastic (both in the sense of "wonderful" and "fanciful") Legend of Abgar, in which King Abgar of Edessa (likely Abgar V, if a real, historical, person is in view) writes to Jesus, asking him to come and heal him of his ailments and offering to give him asylum in his kingdom. If that was all that we had the story might be plausible: it is not incredible that Jesus's fame spread to Edessa. Orbis tells me that you can make the round trip from Jerusalem to Edessa in about five weeks, and about the same from Damascus to Edessa. The possibility that Abgar, sitting in Edessa, could have heard about Jesus, operating in the Galilee and to a lesser extent Judea and the Decapolis, is not far-fetched, nor is the idea that a desperately ill monarch might reach out to any miracle-worker of whom he hears in the hope of being cured. Yet this is not all that we have, and the whole should give us pause.
What should give us pause is that Jesus sends a reply to Abgar. Eusebius moreover has putative access to a copy of both Abgar's letter and Jesus's reply. Properly speaking, there is no reason to exclude the possibility that Jesus wrote Abgar a letter, perhaps via dictation, but it certainly would be otherwise unprecedented. Moreover, the letter as preserved in EH 1.13 reads as a précis of the post-Easter kerygma. It reads more like someone at some remove trying to sound like Jesus rather than like Jesus himself. It seems highly unlikely that here we have extant, written words from Jesus. Most commentators on Eusebius that I have read seem inclined to think that Eusebius is here the unwitting victim of fraud, and this strikes me as highly likely.
What interests me the most is a story that follows after these letters, in which one Thaddeus, already encountered in 1.12, is sent by Thomas to Abgar in Edessa. Eusebius is copying this explicitly from a no-longer extant source, which he states was found appended to the letters just discussed: together they made up a unit. Thaddeus cures Abgar of his illness, and Abgar facilities his preaching in Edessa. No mention is made in the text quoted of mass conversion in Edessa: not even Abgar is said to convert (although in 2.1 Eusebius states that he did, as did the entire city of Edessa, but this seems to be his inference, not something that he find in his sources). It is such a rich narrative. First, the narrative leads to me conclude that this Thaddeus is not understood to be the one numbered among the Twelve, for two reasons. First, the narrative explicitly identifies Thaddeus as one of the Seventy, thus giving us a source for Eusebius's statement in 1.12 that Thaddeus was among that number. It seems probable that if whomever produced the narrative wanted us to think this was Thaddeus of the Twelve he would have identified him as such. Second, that he is sent by one of the Twelve, Thomas, seems to indicate that he was understood as being subordinate to that group, rather than a member in his own right. With this Thaddeus we are probably dealing not with the member of the Twelve but with an otherwise-unattested but similarly-named individual (it's worth noting that in later versions of this story he is known as Addai).
What interests me the most is the question of whether this story, despite all the obvious fantasy surrounding the letters, might not in fact yield some data about Christianity's early expansion. Edessa is not that far from other places evangelized by the first Christians, such that it is hardly impossible that the Christian message was taken there quite early, perhaps already in the 30s or 40s (the 1.12 narrative mentions that Thaddeus went there in the 340th year of Edessa, or 29 C.E., but since we are also informed that this took place after Jesus's death such a date seems much too early). We have reason to think that Christianity is in Cilicia, Cappadocia, and Syria by this point, all of which are proximate to Edessa, and with the Acts 2 narrative, which mentions peoples from Mesopotamia present at Pentecost, there is good reason to think that there was some expansion in that eastward direction. The truth is, if we didn't have reference to someone like Thaddeus we'd likely have to invent him. The outstanding question is whether some ancient writer did exactly that.
In the final analysis we probably can't ever know with great confidence how exactly this legend originated. There might have been a Christian preacher who went to Edessa in the 30s and 40s, and his work in the region served as the initial impetus for the legend of Abgar. Or there might not have been, and the legend is a wholesale fiction. Thaddeus is the sort of figure beside whom we need to put a question mark: we can't rule out his existence and operations in Edessa, but neither can we definitively rule them in.