"See, the thing is, for this campaign I'd have to upgrade the chosen seeing as the chars are level 35."
Oh, brother.
OK, IMNSHO, D20 starts breaking down completely above level 20 and while the Epic Handbook (which you do own, right?) solves and addresses some of the problems it does not by any stretch address all of them.
One of the bigs problems left unaddressed so far in D20 is the overly simplistic design of the EL, ECL, CR system. The D20 system assumes various types of linearity and equivalence which is just not in fact present.
I'm not familiar with the powers of the Chosen, though I know them to be in 2nd edition quite vast indeed. I strongly suggest that you are going to need to apply a fix to the ECL system for a template applied to a high level character.
Some powers acquired in templates are front ended and go away with time extra HD, bonus to strength, small bonus to dex, small natural armor bonuses (3 or less, scent, small bonuses to move, small racial skill bonuses (2 or less), flat energy resistance, flat spell resistance. If the ECL of the template is largely front ended and the ECL is +3 or less, then a flat increase in ECL is not such a bad thing.
But some powers acquired in templates are NOT fronted ended and do not go away with time but instead continue to scale as character level increases. Such powers typically offer a very slight advantage at first, but over time become more and more important. For instance, bonus to intelligence, bonus to constitution, bonuses to a spell caster's primary attribute, energy immunity, increased spell progression, or natural spell progression that increases with character level, regeneration, fast healing, spell resistance that increases with character level, etc. If the ECL of the template is largely based on top heavy powers, a seemingly well chosen ECL makes the template unplayable at low levels but means that above some level the character is recieving an munchkiny maximizing of ability. In my opinion Half-Celestial is a good example of this, and this is the reason the ECL went up from +3 to +4 on revision. For very high levels, even this is too low.
The best solution is to make top heavy ECL's scale with level. For instance in the case of Half-Celestial, a good ECL might be more like + 1 ECL +1 ECL/5 chacter levels (round fractions up). A first level half-celestial is only suffering a +2 ECL penalty, but a 25th level half-celestial is treated as a 31st level character.
A similar thing probably needs to be done with Chosen of Mystra.
The reverse could also probably occur. A template could be so front heavy that it makes a low level character practically invincible vs. low CR challenges. For instance DR 15/+1 is a highly front ended ability. However, over time DR like that goes away as more an more enemies are capable of overcoming it or have non-weapon attacks to get around it. So you might have in theory a ECL like +5 ECL -1 ECL/10 character levels (minimum +1).
Of course, there is probably a more elegant way to do this, and as soon as I think of it I'll submit an article somewhere.