Does the Eastern Orthodox Church consider belief in the existence of Jesus' soul before the incarnation a heresy?
A good friend of mine who is Eastern Orthodox answered this question for me - he said they DO believe Jesus was present BEFORE the incarnation (assuming I understand your question right). Hence the Hymn of the Only Begotten Son:
To not accept Christ as being present before incarnation would be heretical, as He is the Word of God and was present before creation, and through Him all things were created. See the beginning of John, for example. And some part that escapes my mind in Hebrews.