Shouldn't "He already had left" be accepted as well or is that just bad english? lol
Imagine the sentence was "Ele já tinha ido para cama". I think "He had already gone" fits more situations, but I guess your sentence (probably better written as "He had already left") fits some of them.
"He already had gone" is counted as wrong. Very strange.
Standard English grammar: "adverbs of frequency" go between the auxiliary verb and principal verb.
He already had gone is also correct. But tuey say it's not. That is dumb
In good English writing it's better not to separate the verb, thus, he already had gone should also be accepted.
Not better, but it is acceptable