I'd say around +3 or +4.
The ECL of the half-celestial/half-fiend is +5 (or is it +4?) now, not the +2 published in the MM. This is I believe in both the official erratta, and the ECL article suggestions in Dragon magazine.
While there is no way that a 1st level half-elemental is as powerful as a 5th level character, by the time you hit upper levels the number of free spells and free special abilities regardless of class is simply priceless. And further, the enhanced attributes you have will eventually roughly make up the difference in hit points/BAB that you lose by being 4 levels below your peers.
This is the enherent weakness of a linear ECL system, and hopefully a better system will become standard sometime in the future. Until then, I'd give half elementals +4 ECL (erring on the side of caution until I get a chance to look over the template closely).