Was Nestorius ever formally excommunicated and condemned as a heretic?

Yes. A Roman synod under Pope Celestine I condemned him in 430. In 431 the Council of Ephesus, an ecumenical council, condemned him again, deposed him from the see of Constantinople, and sent him into exile in Egypt. Yes, on both counts, and that is exactly why the error carries his name. The Nestorian heresy is not a label historians invented later; it is the formal verdict of the Church on a named man. Here is what happened. Nestorius was bishop of Constantinople. He objected to calling the Blessed Virgin Theotokos, God-bearer. His argument was that if you call Mary the God-bearer you are saying Jesus has only one nature, a divine nature, so he insisted the Church use Christotokos, Christ-bearer, instead. He published this in his Easter letter of 429. St. Cyril of Alexandria answered that God the Son truly entered the womb of Mary, and therefore she is rightly called Theotokos. The point at stake was never really about Mary, it was about Christ. Deny that the one born of Mary is God, and you have effectively split Christ into two persons instead of confessing one divine Person in two natures. In 430 Nestorius was condemned at a local council in Rome under Pope Celestine I. Nestorius did not accept that and appealed over the pope's head to the emperor Theodosius II. That appeal produced the Council of Ephesus in 431, the third ecumenical council, which condemned and deposed him and sent him into exile in Egypt. The historical record is unusually clear on this. A Byzantine notice about Pope Celestine says that he, "together with St. Cyril, laid low the impious Nestorius, who was blaspheming against the Son of God and the holy Theotokos, through a dogmatic letter full of orthodoxy, and cast him out of the orthodox church." Fifty years later, when the emperor Zeno was trying to patch things up with the Monophysites, even his compromise document the Henoticon had to start by acknowledging "the rule of faith followed by the holy Fathers who met at Ephesus and deposed the impious Nestorius." And two and a half centuries later, at the Third Council of Constantinople, the bishops rehearsed the whole sequence of heresies in one breath: Arius met Nicaea, Macedonius met Damasus and Constantinople, "Nestorius divided Christ but was cast out at Ephesus by Celestine and Cyril," and Eutyches was answered when "Leo roared out of Rome like a lion." The east and the west, the friends of Chalcedon and its enemies, all agree that Nestorius was deposed and anathematized. You can also see how binding the condemnation was by what came after. Pope Leo the Great required bishops to condemn Nestorius and Eutyches together as a test of orthodoxy; when two eastern priests, Basil and John, were accused of heresy and traveled all the way to Rome, they cleared themselves precisely by condemning "both the Nestorian and Eutychian heresies." When the writings of Theodore of Mopsuestia, the master of Nestorius, were carried into Armenia, three bishops sounded the alarm. Proclus of Constantinople answered with his Tome to the Armenians condemning Nestorianism, and the Armenians received it with enthusiasm. A heresy does not generate that much sustained formal machinery unless it was formally condemned in the first place. One clarification worth making, because people trip over it. Nestorius was deposed as bishop, which is the canonical removal of a man from his office, and he was anathematized, which is the Church's formal declaration that a man stands outside her communion for holding condemned doctrine. Anathema in that era carried the force of what we would now call excommunication with a doctrinal judgment attached. So if someone asks whether there is a piece of paper somewhere that says "Nestorius is excommunicated," the answer is that what exists is better than that: the sentence of an ecumenical council, confirmed by the pope, deposing him and anathematizing his teaching, repeated and reaffirmed by later councils for centuries. That is the highest form of condemnation the Church has. Whether Nestorius personally held everything later called Nestorianism is a question some historians like to reopen. That is a separate matter from what the Church actually did. The Church tried the doctrine, condemned it, and deposed the bishop who was propagating it.