Does the Eastern Orthodox Church consider belief in the existence of Jesus' soul before the incarnation a heresy? Does the Eastern Orthodox Church consider belief in the existence of Jesus' soul before the incarnation a heresy?
The question is imprecise. It can be read as asking the existence of Christ before His incarnation (which is about the divine person) or about the existence of His human soul before incarnation (which is about His human nature). If it's the former the answer is definitively no. Even Arius of Alexandria while denying the Son is of the same essence with the Father he never questioned that the Logos is exist prior to His incarnation. If it's the later the answer is affirmatively yes. At the Fifth Ecumenical Council of Constantinople (553) the heresy of eternal humanity of Christ is condemned:


  If anyone asserts the fabulous pre-existence of souls, and shall
  assert the monstrous restoration which follows from it: let him be
  anathema.
  
  First Anathema Against Origenism, Second Constantinople 553.


The confusion regarding the difference between what constitute a person and a nature. Jesus' human soul came into existence at the moment of His conception by Theotokos. Human soul is assumed by the Logos in His incarnation not prior. Why this is not the case? Because His humanity is not the proto-type of Adam, it's the other way around. His humanity was taken from Adam. He healed our humanity by assuming it. If He has His own humanity then our humanity is not healed because the fallen nature of Adam has not been assumed. This is why His human soul began to exist only after the conception not prior as argued by Origen.