Cyril VI was removed by the EP in concert with the other Orthodox Patriarchs. A recent example of this was the removal of the Patriarch of Jerusalem Ireneos I by the EP on behalf of and in concert with the other Patriarchs in, I think, 2005. It is the authority of the primus to act on behalf of the Patriarchs once they have decided what needs to be done. Of course if its the EP who needs to be removed, that can be done too (and has been).
But whence did the patriarchs get this collective authority? Universal authority in the Church can only be exercised by either the pope or the entire college of bishops. Even if they are in agreement the patriarchs only have authority over their own patriarchies; they have no canonical authority to act as a senate of the Church.
But even by your own logic the validity of the excommunication by Constantinople fails. If the Council of Florence can be rejected because it was not accepted by the Laos tou Theou in the East then Chalcedon must rejected because it was not accepted by the Laos tou Theou of Egypt and thus the legitimate Patriarch of Alexandria would be the Coptic patriarch. Thus at the time of Cyril VI's excommunication by Jeremias III of Constantinople only two (Constantinople and Jerusalem [and even the legitimacy of Orthodox Patriarch of Jerusalem is questionable]) of the five historical patriarchs (Rome, Constantinople, Antioch, Alexandria, and Jerusalem) concurred in the act.