"He sent it" is the main action of the sentence. "Having written the letter..." is technically an adverbial phrase, describing the conditions of "he sent...".
Why is 'Estis skribinta la leteron, li sendis ĝin' incorrect? Doesnt the 'having' in 'having written' indicate that we are talking about a point in the past, and the 'written' indicate that, at that point, the action is already done?
Estis skribinta in your example doesn't have a subject. In English, we use a participle adverbially, "Having written the letter...", but in Esperanto, you have to make it explicit that this phrase is an adverbial description of the main idea. That's why it has to be skribinte.