Holy Strike isn't as good as you think, KarinsDad. Let's take level 15. A single normal monster might have, say, around 140 HP? The paladin might have a +5 bonus to Wisdom. With 8 attacks and 4 hits, that's an extra 20 HP, maybe 10 of which is applied to a single target unless you're facing a solo. That 20 damage is the equivalent of two attacks, or one from a striker, and it only matters if the extra attacks required would allow a monster to make an extra attack. It's also entirely possible that a crit or a powerful attack will make the damage overkill, especially when it's spread out against multiple monsters.
Sure overkill is possible. It's possible for Enfeebling Strike as well, but in two ways (too much damage, and giving a dead monster -2 to hit).
When looking at Enfeebling Strike, we know the average monster response attack is only changed by 10% if the attack hits.
So taking your 140 hit point monster and a 15th level Paladin averaging D8 (Longsword) +1 (feat) + 3 (magic) +7 (Cha or Str) ~= 16 points of damage. It takes 9 successful Enfeebling Strike hits to kill the monster. At ~21 points of damage with Holy Strike, it takes 7 successful hits.
Note: Not including criticals. Criticals increase the damage by 3 here 1 round in 20, so it is mostly white noise for this example. And, this does not include Encounter powers, etc. It is merely a comparison of Enfeebling Strike multiple rounds vs. Holy Strike.
With Holy Strike, the combat takes 78% of the time as it does with Enfeebling Strike. 14 rounds instead of 18 (at 50% chance to hit). 4 rounds of the monster being dead means 2 times (monster has ~50% chance to hit) that the Paladin does not get hit in those last 4 rounds.
The monster, on the other hand, is only going to have an extra miss one time in 10 with Enfeebling Strike. So, the Paladin hits 9 rounds out of 18 with Enfeebling Strike and gets missed less than once on average in return (and on the 9th attack, the monster is dead, so giving it a -2 is irrelevant, the Enfeebling Strike equivalent of overkill damage that you mentioned).
With Holy Strike, the Paladin gets missed twice (due to the monster being dead) vs. with Enfeebling Strike, the Paladin gets missed 0.8 times (or less than once due to the monster being enfeebled).
Granted, one extra missed attack could also mean an extra missed condition. Or, the monster attack might not have an additional effect. Stopping the combat 4 rounds early and not taking 1.2 times the monster's damage is probably worth more than taking a condition since most conditions only last for a round, but it all depends on what it is.
On the other hand, longer combats are bad for PCs in 4E. It gives the DM more of an opportunity to roll well.
This was an example with a Longsword. It doesn't change much with a bigger weapon, but feel free to do the math for yourself.
I'm not stating that Holy Strike is strong. I'm stating that Holy Strike is typically stronger and more useful than Enfeebling Strike. Enfeebling Strike has some corner case utlity for protecting an ally and can once in a blue moon, stop a PC from taking damage and possibly an effect, but again, that is only one time in 10 that it is successful. And then, only if the Paladin hits with it, so one enemy attack in 20 does it actually protect and that's only for rounds the Paladin uses Enfeebling Strike instead of some other power.