Some Orthodox say that the Catholic baptism is valid, others say that it isn't. Then the waters are muddied further by people who say that Catholic baptisms will be accepted by economia (a dispensation), but then this camp is divided into two factions: those who think that we accept the Catholic baptism and add whatever is lacking, and on the other hand those who think that the Catholic baptism has absolutely nothing to it (ie. no sacramental grace) except the outward form.
Discerning this issue on the basis of early Patristic texts is difficult, because ostensibly
what one finds is a series of contradictory practices.
St.Cyprian actually has quite a bit to say about this topic which is quite perceptive and well argued. While some accuse St.Cyprian of "introducing a new practice" (insisting on the Baptism of all converts, including those coming from sects and heresies), this is based upon a misreading of him and a rather superficial "taking for granted" of what his contemporary critics said on the topic (namely, their portrayal of their practices and the interpretation they were giving them as being "universal".) It's quite clear when one actually reads St.Cyprian's epistles on this subject, that he was simply arguing for a practice which was normal in Carthage and in much of Christendom (it's important to note also that St.Cyprian is not an "Eastern" Father, anymore than St.Augustine is.)
Part of the confusion amongst early Christians on this topic had much to do with the rather superficial reasoning which those in Rome and some other parts of the West. For example, St.Cyprian was confronted by Pope Stephen (and those in agreement with him) with the reasoning that their own practice (of never "re"-Baptizing converts from heresies) was "ancient." St.Cyprian wrote on this matter in the middle of the third century - the Church of the New Testament was not even three centuries old, so "ancient" in context did not have the significance we would now apply to the term. St.Cyprian rightly pointed out, that the origins of "economic reception" were not in the reception of converts who had been taught and baptized by sectarians, but of those who had begun as Orthodox laymen and clergy but who departed from the unity of the Church at some later point, only to eventually be reconciled. In such circumstances, people obviously were not Baptized again, but were simply received as penitents, and were Chrismated to "re-energize" that which had become muted by their defection from the Body of Christ. St.Cyprian had no issues with this, and would have called doing otherwise an obvious sacrelige.However
the matter became more complicated in the case of those who were never
members of the Bride of Christ to begin with, but rather were baptized and ordained by those who had departed from the Church, or even more remotely, by bishops and presybters who were themselves successors to those who had abandoned Orthodoxy.
The Popes and the Latins were basically arguing that the sacramental form is itself sacred and ecclessiastical, no matter who is administering it. As such, it shouldn't be "repeated." Many of the other arguments put in favour of this though, were extremely poor - including what amounted to "well, certain heretics don't re-baptize Orthodox who go over to them, so we shouldn't either." Or conversly, "the Novations practice re-baptism, so we shouldn't." This is curious "reasoning" if one even wants to call it that - St.Cyprian put it quite aptly when he said (paraphrase) "monkeys imitate men, but that doesn't make them human, nor does it mean we should in turn stop acting human!"
It's important to understand that Rome's position was quite liberal at one point, and the language they used was not at all precise or cautious about making the necessary distinctions. Phrases like heretical baptism having the "grace of baptism" would be said on one hand, while the Romans themselves were still using liturgical texts which plainly stated (in the baptismal rite) that one approached the Church
with the request of receiving the remission of sins - which was it? This is an especially good question, when one considers that the Romans were nonetheless quite keen on saying that heretics were not part of the Church. Many patrologists have observed that in the period when this controversy raged, Rome couldn't exactly be said to have been known for it's erudation. To their credit, the Roman Church tended to be quite conservative at that time in it's practices and in maintaining the pre-Nicene symbolic formulas it had inherited - but this attachment to forms was often reflexive and unthinking, even in the face of changing circumstances.
OTOH. when the Ecumenical Councils started rolling out canons regarding the treatment of converts from heresy, we notice they're quite a bit more restrictive than the Roman polemic of the third century. Additionally, it is quite difficult to pin down a consistant "dogmatic criterion" for whose baptisms the Church was willing to accept and whose they were not. While the more grotesque heresies were always excluded (especially those which mangled the baptismal rite itself), nothing like the modern RC criteria could be projected upon them, because they were primarily pastoral and operated under different assumptions. For example, the RC teaching on "validity" would be unable to account for why the Great Councils allowed for Arians
to be received by economy - they were not even Trinitarians! It's precisely on that basis that modern Catholicism will not accept Mormon baptisms, even though the ceremony itself is extrensically pretty "normal" and does mention "the Father, Son and Holy Spirit." In 1992, (then) Cardinal Ratzinger issued a response on behalf of the CDF on this subject, explaining that despite the fact that the Mormons use a ceremony and wording which looks amicable to Catholicism, their doctrinal understanding is such that it makes the acceptance of their baptisms as "valid" impossible. Yet, Rome signed onto doing something much like "accepting Mormon baptism" back in the fourth century, along with the rest of Orthodox Christendom.
It is interesting to note that with time, the Roman language on this subject became a little more precise. St.Leo the Great was pretty clear in stating that the "mysteries have withdrawn themselves" from heretics, and that in the case of their baptisms at least (when they follow the Orthodox form) they are "bare form." Yet, because he believed the form of the rite itself is sacred and ecclessiastical, it ought not to be repeated, especially since he believed such would create impediments in many to convert away from heresy due to "timidity". OTOH. the view of St.Basil the Great took hold elsewhere, which while citing the authority of St.Cyprian on this matter, also recognized the utility of admitting some
heretically administered baptisms. The logic in such a view seems to be that while it is true only those departing from the Church themselves have with them genuine baptisms and ordinations, the sects they form and adhere to as a whole do still have some kind of relationship to the Church...it's a broken one, but there is something there, even if it is simply key articles of faith and praxis. Thus, just as the Church restores those who in their own lifetimes left the Church, She can also restore members of communities which had in the past left the Church - She "energizes" what was imposed only as a vessel.
Where the greater part of the Church would have disagreed with Rome and those who were coming under her influence in Western Europe (a process which actually wasn't completed until the 11th century, when the English stormed into Ireland with a Papal blessing and suppressed the last strongholds of Celtic Christianity), is over the idea that it is impossibe to receive converts from heterodoxy via Holy Baptism were economy is possible, let alone going so far as to call this "sacreligious" (as it would be in the case of trying to re-baptize someone who had already received a canonical Baptism at the hands of an Orthodox Priest.) Unfortunately, this issue was never fully resolved between Rome (and it's increasing western "holdings") and the rest of Christendom before more obvious disagreements and breakdowns in relations began to occur in the latter part of the first millenia A.D.
A further complication is that Rome would eventually receive as dogmatic fact
the speculative theology of St.Augustine of Hippo on this topic, as others in this thread have mentioned. It is St.Augustine who introduces a sharp distinction between "sacramental character" and "grace", insisting that the former is present wherever certain conditions are met, but the latter only within the Church. He further reasoned that what stopped this distinct "grace" from being effective in those "received" by heretics was fundamentally a moral impediment in such a "neophyte." To his credit, St.Augustine submitted all such speculative writings to the judgement of the "Church Universal" - and it seems quite apparent, that this is one matter where She has shown Herself to be in disagreement with him.
This is beside the fact that the Augustinian theory (which was put forward mainly as a reaction to the practice of the Donatist and other Puritan sects, of "baptizing" Orthodox Christians who defected to them) is itself problematic in it's application. While modern Vatican "ecumenical sensitivity" has in the last 40 years pretty much made this a moot point (mainly by simply avoiding the issue), the fact of the matter is that even while cherishing the old Augustinian/Scholastic qualifications of "form, matter, and intent" as being the substance of a valid sacrament, rigorous Roman Catholic theologians had good reasons (within that paradigm) to doubt the validity of the baptisms of those they often received into the fold. This is why so many confessional Protestants were simply "conditionally baptized" - a practice where by the priest says "if you are not baptized, I baptize you in the name...". Of course such a rite is not at all apostolic in nature, and really only obfuscates an obvious problem with the Augustinian formula; for when scrutinized, it becomes pretty clear that the heterodox (real or subjective to the Roman Catholic p.o.v.) do not have the same "intentions" as a Roman Catholic priest would. They don't even necessarily believe baptism gives the remission of sins; and when they desire to integrate people into "the Church", just what "church" are they talking about? If you asked them, they'd be very clear they didn't believe it was one "headed by the Pope", etc. It would also seem the Roman Catholic take on "validity" has long ago come to reject the essentially priestly
nature of Baptism - an idea which is very plainly accepted by all
of the Fathers. The last time I checked, the RCC doesn't believe the Lutherans, Anglicans, etc. even have "priests".
Of course nothing I've said here is meant to imply that we can know "as a matter of faith" that there is no mysteriological grace outside of the visible boundaries of the Church under any circumstances. "God is God" and can obviously do whatever He wishes. One may even have strong "suspicions" on this matter. But just as presumption
is erroneous (and even sinful!) when we commit to it with regard to ourselves (ex. continuing in sin, with the expectation of "repenting" and trying to ammend one's life at a later date), it is also erroneous in the case of those who are by all sensible indicators outside of the Church. Strictly speaking, if the situation were otherwise, we would have no reason whatsoever
to insist that the heterodox correct their ways and return to the fold. The Church is not a society for know-it-alls or the "correctest of Christians", but is the sole Ark of Salvation - it is the only place where we know men can work out their salvation. She has received the great promises of Christ - all that is outside of this, is quite literally "in God's hands."