To my understanding, both hold the meaning of "already happened long ago". What are the nuances though? Are they interchangeable?
他早已打定主意了。 (He made up his mind long ago.)
他早就搬走了。 (He moved out long ago.)
早已 and 早就 are different. They can be exchangeable in practice and may or may not have the same meaning. But their grammar structure are different.
他搬走了.(He moved) (To answer what happened to him?)
他已经搬走了.(Since he moved, he is no longer here)
他早已经搬走了.(1) (Since he moved, he is no longer here. That happened long time ago.)
他早已搬走了.(same as 1)
他早搬走了.(He moved)(That happened long time ago.)
他早就搬走了.(He moved)(I am sure that happened long time ago.) (How come you do not even know it ??? )
早已 has the basic meaning of 已经. The combination logic is the 早 is used to modify 已经.
早就 has the basic meaning of 早 as adverb to modify the verb 搬走. 就 is to emphasize and to be very sure about it.
早已 is more formal. It is seldom used in modern Cn Lang. In general, it brings you negative emotion. (Something/Somebody has gone/disappeared/left)
早就 has some deeper meaning such as pride, regret, impatient, etc. It broadly used in modern Cn Lang.
我早就把早餐做好了 - I have cooked our breakfast already. [PRIDE]
他早就去世了 - He has been dead already. (I missed him so much.) [REGRET]
早就做完了 - It is done already (and I don't want to talk about it any more since I have things to do. I have no time talking with you). [IMPATIENT]
These two words are the same meaning.Both mean something are already end in long time. But '早已' is used in written form more often.And ‘早就' sometime sub mean：complain something doing too late.
你怎么还不走？他早就走了。tell him keep up quickly.
你怎么现在才来？他早就走了。You are too slow.
To your specific question:
早已 is more literal. It existed in classical poems, e.g., "小荷才露尖尖角，蜻蜓早已立上头".
早就 is more verbal. It is widely existing in modern Chinese.
Nowadays, there is no difference in meaning, unless you are studying classical Chinese.
Spiting the words, 已 and 就 are just like the relationship between 早已 and 早就, one is more literal while they other is more verbal.
As other combinations like 已经, 早已经, these are already off topic.