Why did the mid-early church consider the Gospel of Matthew to be reliable?

First, it is important to realize that ancient writers almost never quoted anything in the way we do today. The normal way to "quote" was via allusion - the reader was expected to recognize the author's intent via a shared background. Even when quotes are explicit ("it is written", they are often not exact (ranging from free paraphrase to "memory error" - it was not easy to look up a passage in a text as there were no chapters, verse numbers etc.). Even in those cases, the author is not normally stated. Some OT examples from 1 Clement will be illustrative (since he surely considered the OT canonical).

Every kind of honour and happiness was bestowed upon you, and then was fulfilled that which is written, "My beloved ate and drank, and was enlarged and became fat, and kicked." (Ch 3)

This is a clearly intended as a quote, yet compare to Deut 32:15 (the source; note OT quotes will be from Brenton's LXX translation since church fathers likely used the LXX and modern translations generally use the Masoretic text):

So Jacob ate and was filled, and the beloved one kicked; he grew fat, he became thick and broad; then he forsook the God that made him, and departed from God his Saviour.

As you can see, it is partially very close and partially paraphrase. Next

Envy has alienated wives from their husbands, and changed that saying of our father Adam, This is now bone of my bones, and flesh of my flesh.

This is a clear allusion to Genesis 2:6:

And Adam said, This now is bone of my bones, and flesh of my flesh

but note that Clement does not say "as written by Moses" or "as written in the Torah" or even "as scripture says". He simply expects his readers to get the reference.

One more:

The ministers of the grace of God have, by the Holy Spirit, spoken of repentance; and the Lord of all things has himself declared with an oath regarding it, "As I live, says the Lord, I desire not the death of the sinner, but rather his repentance;"

This is a clear allusion to Ezekiel 33:11:

Say to them, Thus saith the Lord; As I live, I desire not the death of the ungodly, as that the ungodly should turn from his way and live

but Clement does not introduce it as "according to the prophet Isiah" but rather attributes it to God himself.

In all, Clement makes more than 100 possible allusions to the Old Testament. In none of them does he say something like "in the book of X" and the majority he doesn't even introduce as scripture. If he didn't quote OT scripture in a way modern people would consider "unambiguous", we shouldn't expect him to quote NT scripture this way. Additionally, with Matthew there is the difficulty of identifying which gospel he is alluding to when a story is shared by multiple gospels. Even so, let's take a look.

Clement writes (ch 46):

Remember the words of our Lord Jesus Christ, how He said, "Woe to that man [by whom offenses come]! It were better for him that he had never been born, than that he should cast a stumbling-block before one of my elect. Yea, it were better for him that a millstone should be hung about [his neck], and he should be sunk in the depths of the sea, than that he should cast a stumbling-block before one of my little ones."

which appears to be a conflation (Clement conflates OT text quite often - he has no problem combining saying of God from one text with thus of another under one quote) of Matt 26:23 "But woe to that man who betrays the Son of Man! It would be better for him if he had not been born." (NIV) and Matt 18:6 "If anyone causes one of these little ones—those who believe in me—to stumble, it would be better for them to have a large millstone hung around their neck and to be drowned in the depths of the sea."

A couple other passage thought possible to likely to literately dependent of Matthew specifically (due to Greek used) include Clement 13 compared to Matthew's account of the Sermon on the Mount; Clement 24 to Matthew's parable of the sower; and Clement 16 to Matthew 11:29-20. There are many, many other allusions and quotes of NT texts, including several possible Matthew quotes.

Individually, many allusions can easily be disputed. Collectively, it is very hard to explain the high amount of word agreement (in Greek) other than by the hypothesis of written gospels (esp. Matthew) being used as sources. Add to this, the following quote (Clem 13)

and let us act according to that which is written (for the Holy Spirit says, Let not the wise man glory in his wisdom, neither let the mighty man glory in his might, neither let the rich man glory in his riches; but let him that glories glory in the Lord, in diligently seeking Him, and doing judgment and righteousness), being especially mindful of the words of the Lord Jesus which He spoke teaching us meekness and long-suffering.

where Clement clearly says the words of Jesus come from written scripture.

To keep this answer somewhat reasonable in length, I'm not going to go through other early documents in detail but just quote some scholars instead:

• Didache:

Apart from Did. 1. 3-2. 1, almost all the echoes of the synoptic tradition which appear in the Didache can be explained as deriving from Matthew... In virtually every instance where there are synoptic parallels, the version in the Didache is closest to the Matthean version. Moreover, in some instances the Didache appears to reflect elements of Matthew's redactional activity, and hence to presuppose Matthew's finished gospel rather than just Matthew's traditions. (The Reception of the New Testament in the Apostolic Fathers by Andrew Gregory and Christopher Tuckett)

• Barnabas:

But in spite of all of these arguments, it still remains the case that the closest existing text to Barn. 4. 14 in all known literature is Matt. 22. 14, and one senses that attempts to argue for independence from Matthew are partly motivated by a desire to avoid the implication of the formula citandi which introduces the relevant words: namely, that the author of Barnabas regarded Matthew as scriptural... If, as was implied in my discussion of Barn. 4.14, it is the case that the author of Barnabas did know Matthew, then does it make sense to state that a series of Greek words which come very close to words found in Matthew go back to a tradition independent of that Gospel? (ibid.)

• Ignatius:

Ignatius indicates only a slight awareness of the Gospels of Mark and Luke, and he seems familiar with Johannine themes, if not John's Gospel itself. It is clear, however, that the Gospel of Matthew is his preferred text, a gospel upon which he is dependent for many of his arguments. (The Apostolic Fathers and the New Testament by Clayton Jefford)

• Polycarp

Helmut Koester is usually associated with the view that knowledge of the written Gospels cannot be proven in the Apostolic Fathers... Neverthe­less, even Koester thinks that in Polycarp's letter there is evidence of the influence of the written gospels (in particular Matthew and Luke) during a period when orality was still important. (Polycarp and Paul: An Analysis of their Literary and Theological Relationship in Light of Polycarp's Use of Biblical and Extra-Biblical Literature by Kenneth Berding)

Note: Polycarp (writing around 108) is often considered the first clear witness to the existence of written gospels.

• 2nd Clement (written by a different author than 1st Clement)

At a number of places 2 Clement presupposes the redactional activity of both Matthew and Luke in traditions of the sayings of Jesus which they have in common. At the very least, this suggests that the tradition on which 2 Clement is based for its knowledge of Jesus tradition represents a stage which presupposes the finished gospels of both Matthew and Luke. (Gregory & Tuckett)

And these are just the sources that predate 150 AD...

Turning the the explicit mentions. The first explicit mention is Papias. Unfortunately, only a small part of his work has survived through quotes in other works. In what we do have, he mentions Mark, Matthew, John, and several NT letters (but not Luke). On Matthew, he says:

Matthew compiled the Oracles [of Jesus] in the Hebrew language, and everyone translated them as well as he could.

Thus passage is famously ambiguous and without the context we can't draw any firm conclusions. Nevertheless, we know Papias' purpose in general was to put the oral tradition into writing. ("But I shall not hesitate to furnish you, along with my explanations, with all that in days gone by I carefully learned from the Presbyters and have carefully recalled, for I can guarantee its truth.") As I said in my previous answer, the earliest church valued the oral tradition above the written tradition, preferring to carefully pass the teachings from one generation to the next. However, as time went on, the need to write things down grew stronger.

Papias appears to explaining where the Gospels came from. He says the first step was Matthew writing down "oracles" (likely sayings) of Jesus. Sometimes critics dismiss this statement out-of-hand since the Gospel of Matthew was not written in Hebrew/Aramaic, but I think this is done too hastily. By all accounts, the Gospel was written at least 70 years (~100 in my view) before Papias, and as demonstrated above some form of it was quoted/alluded to by many writers. It defies common sense to say Papias was unaware of the Greek Matthew and yet he says Matthew originally wrote something in Hebrew/Aramaic. One plausible explanation is that he is intending to say Matthew wrote down some quotes of Jesus and these quotes were then used by gospel writers. By the ancient understanding of authorship, Matthew could then be viewed as the author of the Gospel even if he didn't directly compile it (although there is no reason to assume he did not to this himself.) But again, we can't draw a firm conclusion about what Papias means.

The next source to consider is the Muratorian Canon. Written about 170 AD, this is the first extant (written) attempt at defining the canon. The first few lines are lost, so it technically does not mention Matthew. However, it does state the third Gospel is Luke and the fourth John. It is perfectly logically to think it originally also talked of Matthew and Mark, and I don't think anyone would really dispute that is what it did. Of course we don't know what it said about Matthew specifically, but we do get some clues about how canonicity in general:

• Accepted works are tied to Apostles in some fashion.

On non-accepted books:

There is current also [an epistle] to the Laodiceans, [and] another to the Alexandrians, [both] forged in Paul's name to [further] the heresy of Marcion, and several others which cannot be received into the catholic Church — for it is not fitting that gall be mixed with honey.

• These works are seen as appalling, both on content and their forged authorship.

We receive only the apocalypses of John and Peter, though some of us are not willing that the latter be read in church.

• Although the author of the Muratorian fragment accepts the Apocalypse of Peter, he acknowledges that others did not. This demonstrates that usage in church services was a factor.

But Hermas wrote the Shepherd very recently, in our times... it cannot be read publicly to the people in church either among the Prophets, whose number is complete, or among the Apostles, for it is after [their] time.

• In the ellipsed part of this quote, the author acknowledges the text's spiritual usefulness, but he nonetheless says it cannot be accepted because it is a recent work without apostolic authority. Being orthodox in teaching was insufficient.

Next is Iranaeus, who as you correctly state, clearly quotes and attributes the Gospel of Matthew to the apostle Matthew. This is what he says about the gospel:

Matthew also published a gospel in writing among the Hebrews in their own language, while Peter & Paul were preaching the gospel and founding the church in Rome. (Against Heresies 3.1.1)

It is clear that he equates this book with the Greek Matthew because he quotes from it extensively and the quotes match the book we have today ... On another note, a (now-deleted) comment suggested Iranaeus decided there must be four gospels and picked which ones to keep. This very much has things backwards to my mind. Here is what he says:

It is not possible that the Gospels can be either more or fewer in number than they are. For, since there are four zones of the world ... it is fitting that she should have four pillars, breathing out immortality on every side. (Against Heresies 3.13.8)

In context, it is clear to me that he was not defining a criteria and picking gospels to fit it, but rather he was inventing an explanation for why the accepted canon had four Gospels.

Another thing to consider is many of the second century apocryphal writings that have survived to the present day mostly try to fill in the periods "missing" from the NT gospels & Acts - Jesus' childhood; Mary's family history; Judas' motives; Paul's activity after the end of Acts; the preaching of the other members of the 12 who don't have attributed works; and so on. This strongly suggests that the gospels were already considered canonical and thus the known history "untouchable".

One final thing to consider is that in the second century harmonies of the gospels started to appear. There was a desire by some believers to have a single uniform account (just as there is today) and yet the church ultimately resisted this desire and preserved the originals (despite the harmonizations being orthodox). Scholars believe Justin (c. 150) either wrote or relied on a harmony of the first three Gospels, and it is known for sure that Tatian (c. 170) wrote a harmony of the four gospels (it has survived to the present). Tatian does not use any other text (e.g. known apocrypha), but does add a few filler passages to connect the various stories into a single sequence. This shows rather conclusively that he viewed the four canonical gospels, and only those, as authentic.

None of the above proves, or even attempts to argue, that Matthew wrote Matthew (that would be a different post entirely). Instead, it shows that the early church viewed him as the author. Apostolic authority (direct or indirect such as Mark and Luke) was essential for canonization. However, it was not sufficient. A text also had to be orthodox in teaching (i.e. compatible with other accepted documents) and be in general use. On the last criteria especially Matthew excels, as it was the most quoted/alluded to text in the early church.

Below is my answer to the original question: "What are the arguments for Matthew's canonicity that don't appeal to Matthean authorship or the authority of the church?" I have leaving it as is, because it is still valid answer to that part of the question (and good information), although not all of it makes sense as a reply to the edited question.

First, I think it is important to emphasize that no church leader or set of leaders sat down one day and decided that X was in and Y was out. Instead it was decided over time by the Church (fellowship of all believers) through use of some sources and disuse of others. Early leaders, of course, had some influence over what entered the canon, but no single person, congregation, or group of people decided this.

We have some extant writings about what criteria were used to decide matters. For example, Tertullian, writing in objection to Marcion (Contra Marcion, Book 4, Ch 5), says that his followers "subvert [the gospel] by shameless tampering" and says

Such are the summary arguments which we use, when we take up arms against heretics for the faith of the gospel, maintaining both that order of periods, which rules that a late date is the mark of forgers, and that authority of churches which lends support to the tradition of the apostles; because truth must needs precede the forgery, and proceed straight from those by whom it has been handed on.

Various factors enter into the criteria recorded by various Church fathers:

• is the document internally consistent,
• is it teaching orthodoxy,
• was it accepted by early churches,
• and Apostolic authorship is seen as key.

This can be seen, for example, in the dismissal of an elder who confessed to writing The Acts of Paul and Thecla (Tertullian, On Baptism, Ch 17), despite the work being perfectly orthodox. In short, there was no such thing as a "pious fraud" who was accepted by the church. If the early Church believed Matthew was not written by Matthew, it would have never been accepted. You cannot separate the two ideas.

Turning specifically to Matthew, it was the most quoted NT work during the first two centuries and was rejected by no known group, heretical or orthodox, except for Marcion (who rejected all but his own edited versions of Paul's letters and Luke). If any work can be considered canonical by the early church, it is Matthew. It was not accepted because of the testimony of Papias (and just because he is the first extant witness of Matthean authorship, does not mean he was the first), but rather was universally viewed as coming from Matthew the apostle.

I would strongly caution against rejecting a work because of "difficulties". Of course if you remove any gospel, the number of apparent contradictions will decrease. However, minor contradictions show the reliability of text, not the opposite. Real eyewitness testimony is marked by such differences; faked or non-independent accounts are not. I would also be very cautious about accepting pseudographical claims lightly. The case lies on a few far from certain facts and stand contrary to every source in antiquity. I cannot go into detail here (ask another question if you like), but suffice it to say that the burden of proof should lie with those claiming pseudography (due to the frequent and early testimony to the contrary and the demonstrated disdain for the practice) and the case has not been proven.

In summary, to answer your question: besides apostolic authorship and church authority, canonicity can be argued on early and frequent use, the acceptance by early believers, internal consistency, and the orthodoxy of Matthew. However, in the views of the early Church, apostolic authorship is also essential.