Why did Clement and Eusebius believe that Paul was married?

Definitely an interesting find, Nathaniel. Whether Clement truly meant to imply that Paul had a 'wife,' in my opinion is a 'Maybe'(but probably not). In Clement's era Paul was viewed as a celibate who had many female disciples.

As Thaddeus explains the greeting is in reference to Philippians 4.3. The term suzygos is a common term for spouse (in Greek) but generically only means to be 'yoked'.

I must thank Susan in finding the original Greek term used by Clement suzygos (translated as consort in English, conjugem in the Latin text) which differs from the word he uses for wife (uxorem in Latin translations yunaika in Greek).

The 1 COR 9.5 verse speak of 'sister wives' (in actuality the greek word for wife and woman is interchangeable hence possible translation as believing wife or women who are sisters). It seems apparent when you read the entirety of Clement's commentary in Stromateis bk3, Clement is dealing with various sects, some participated in sexual immorality like passing their wives around while at the other end of the spectrum some were highly ascetic who did not even want to communicate with women and had a warped extremist view of celibacy. Here is Clement in context:

51. ... Therefore there is nothing meritorious about abstinence from marriage unless it arises from love to God. At any rate the blessed Paul says of those who revile marriage: "In the last times some shall depart from the faith, turning to spirits of error and doctrines inspired by daemons, forbidding to marry and commanding abstinence from food." And again he says: "Let no one disqualify you by demanding self-imposed ascetic practices and severe treatment of the body." And the same writer has this also: "Are you bound to a wife? Do not seek to be separated from her? Are you free from any wife? Do not seek to find one." And again: "Let every man have his own wife lest Satan tempt you."

52. ... But whereas they say that they are superior to them in behaviour and conduct, they cannot even be compared with them in their deeds. "He who does not eat," then, "let him not despise him who eats; and he who eats let him not judge him who does not eat; for God has accepted him." Moreover, the Lord says of himself: "John came neither eating nor drinking, and they say, He has a devil. The Son of man came eating and drinking and they say, Behold a gluttonous man and a wine-bibber, a friend of publicans and a sinner." Or do they also scorn the apostles? Peter and Philip had children, and Philip gave his daughters in marriage.

53. Even Paul did not hesitate in one letter to address his consort (Phil 4.13). The only reason why he did not take her about with him was that it would have been an inconvenience for his ministry. Accordingly he says in a letter: "Have we not a right to take about with us a wife that is a sister like the other apostles?" But the latter, in accordance with their particular ministry, devoted themselves to preaching without any distraction, and took their wives with them not as women with whom they had marriage relations, but as sisters, that they might be their fellow-ministers in dealing with housewives. It was through them that the Lord's teaching penetrated also the women's quarters without any scandal being aroused. We also know the directions about women deacons which are given by the noble Paul in his second letter to Timothy. Furthermore, the selfsame man cried aloud that "the kingdom of God does not consist in food and drink," not indeed in abstinence from wine and meat, "but in righteousness, peace, and joy in the Holy Spirit."

Stromata, Bk3 ch 6

Paul was also known for attracting many female followers and converts. Aside from Philipians 4.3 There was Lydia in(Acts 16.14) a converted due to Paul's preaching. In Romans 16 he greets multiple women who were fellow consorts. It specifically mentions in Acts that noble women were especially receptive to Paul's preaching:

Then Paul, as his custom was, went in to them, and for three Sabbaths reasoned with them from the Scriptures, explaining and demonstrating that the Christ had to suffer and rise again from the dead, and saying, “This Jesus whom I preach to you is the Christ.” And some of them were persuaded; and a great multitude of the devout Greeks, and not a few of the leading women, joined Paul and Silas. (Acts 17.2-4 NKJV)

In around 190 AD there was also circulating the apocryphal Acts of Paul and Thecla. Thecla was a woman engaged to a pagan man who was converted by Paul. She broke off her marriage and vowed a life of celibacy. The thing is even though she is presented as a fellow minister and follower of Paul, he is usually absent from her adventures. Thecla contends for the faith on her own. This echoes Clement's assertion that Paul didn't like taking 'sisters' with him in his ministry. It's quite possible that the 'consort' Clement had in mine was similar to a Thecla. This is plausible when we look at her fame within Paul's ministry in the late 2nd-4th century.

If Clement did believe he was lawfully wedded it would be based on interpeting sysyge gnisios as 'genuine spouse' and coupling it with 1Cor 7.29, that since the time is short those that are married should act as if they are not, so he does not bring her along like the other apostles.

What an interesting find! The Biblical text in view is indeed 1 Cor 9. The key to understanding how they derived this interpretation is knowing what Clement and Eusebius meant by the words translated in the question as "greet" and "wife".

Clement explains the relationship between the apostles and women (Stromatum III, 53; Greek, English):

But the [apostles] devoted themselves to preaching without any distraction, and took their wives with them not as women with whom they had marriage relations, but as sisters, that they might be their fellow-ministers in dealing with housewives.

This is the sort of relationship Clement refers to in the quote in the question; he believes Paul to have had such a wife whom he chose not to take with him on his missionary journeys.

Eusebius quotes Clement:

Παῦλος οὐκ ὀκνεῖ ἔν τινι ἐπιστολῇ τὴν αὐτοῦ προσαγορεῦσαι σύζυγον, ἣν οὐ περιεκόμιζεν διὰ τὸ τῆς ὑπηρεσίας εὐσταλές.

Paul did not hesitate in one of his letter to προσαγορεῦσαι his consort whom he did not take around with him for the sake of convenience in his ministry.

(One word left untranslated pending discussion below.) The Greek edition of Eusebius (HUP, 1926) indicates via footnotes that 1 Cor 9 and Clement's Stromatum III are in view. Immediately after the bit quoted by Eusebius, Clement himself confirms the reference to 1 Cor 9 (Greek, English):

λεγει ουν εν τινι επιστολη ουκ εχομεν εξουσιαν αδελφην γυναικα περιαγειν, ως και οι λοιποι αποστολοι?

Accordingly he says in a letter: "Have we not a right to take about with us a wife that is a sister like the other apostles?"

This is a direct quote of 1 Cor 9:5. The phrase translated "a wife that is a sister" in the quote from Clement (αδελφην γυναικα) is nearly universally accepted to mean "a wife who is Christian" or "a believing wife", hence the English translations of 1 Corinthians. The Greek of Clement is identical to that of Paul.

The only remaining problem is that there is no "greeting” evident in 1 Cor 9. The word translated “address" (from both Clement and Eusebius) is προσαγορεύω.² It can refer to a greeting, but also (BDAG):

to refer to someone by name or some other term, call, name, designate

It need not require a second person address ("greeting"), then. Here it probably simply refers to the "mention" or "naming" of such a woman.

Clement and Eusebius understand 1 Cor 9:5 as a reference to a wife who was a companion and fellow minister but without marital relations. In light of verse 12, they concluded that Paul (and others with him) had chosen not to take such women with them (οὐκ ἐχρησάμεθα τῇ ἐξουσίᾳ ταύτῃ = we have not made use of this right) in order not to "put an obstacle in the way of [their] ministry".

_{1. Anthony C. Thiselton, The First Epistle to the Corinthians: a Commentary on the Greek Text (NIGTC; Grand Rapids: Eerdmans, 2000), 680.}

_{2. For those who care, the word is found in the NT only in Hebrews 5:10, where it is most naturally read as a designation rather than a greeting.}