Although a bit off-topic, the Neverwinter Nights expansion, Shadows of Undrentide had a special Paladin-only quest which let them obtain a Holy Avenger. Unfortunately, it came at a fairly low level (IIRC, 7th or 8th), and after getting it, the game becomes stupidly easy. There was other special equipment available for Paladins as well, and in conjunction it made the game totally unchallenging.
In a typical D&D campaign, I'd estimate that a Paladin shouldn't get one, at least permanently, until they are well into the double-digit levels. If you want to loan one to a lower level paladin for a single session for some special quest, that might be ok under the right circumstances. Otherwise, keep it away until much, much later.