Not sure if my English is right here but, wouldn't it be correct "I will have left until tomorrow" as well?
No, it wouldn't.
"until" is used for things which have a duration -- "I will stay here until tomorrow", for example. The process of "staying" takes a long time: from now until tomorrow.
But leaving is not something with a long duration. You can't "leave until tomorrow".
Yes now that I re-read it from you, my sentence sounds odd.. so, the "Θα έχω φύγει μέχρι αύριο" is often used? Or could it be simplified by saying "Θα έχω φύγει αύριο" ?