Neither are unpowered, just no one plays them right. And since hardly any are at 50 everyone assumes they suck and they don't.
Flail for paladins
I couldn't do much to a paladin I should have swept the floor with, it made Toten sad. 
Paladins are the best class till you hit 42, then they are bland.
Everyone has a weapon you do not know about, your flamstrike hardly ever blinds at high levels due to saves.
Vs a Warrior type, your unique skill is charge, that is if they cannot counter, as everyone has a main cursed weapon.
Vs a communer, you mostly charge as trying to disarm a shield without blinding them with flamestrike will prove futile.
You cannot even use a chamie due to heroism.
Its one of those classes, that if you wish to actualy get some kills you need that EQ that blinds, poison etc.
And Gentleman, your knolage on Flail is lacking to say the least. 
My elven pally is pretty much the only character I get consistently owned on. Not to say I don't think it's powerful, just pointing out that it seems like every time I get on I die, whereas that just doesn't happen as much with my others.
Paladins are titans. The problem you have is.."How do I dress?"
It's a hard question. To fight vampires, or melee classes you need a solid melee backing, yet to fight shamans you NEED huge saves. When fighting clerics.........well you don't have much chance here, you'll be disabled pretty bad without huge mental saves.
Trying to mix the equipment doesn't really work either, as then you sacrifice AC, and that is really needed as well. And that was my problem with Dyendas. Sure I could survive fairly well, but not anywhere near a clerics survivability. Sure I had more offensive, but I had to dress properly to get it. Then when I would think about it, I just couldn't put a perfect paladin suit together. Clerics just would always come out the logical choice, as they don't have to mix and match their equipment as much. They dont' need a 'perfect suit'.
Paladins are titans. The problem you have is.."How do I dress?"
It's a hard question. To fight vampires, or melee classes you need a solid melee backing, yet to fight shamans you NEED huge saves. When fighting clerics.........well you don't have much chance here, you'll be disabled pretty bad without huge mental saves.
Trying to mix the equipment doesn't really work either, as then you sacrifice AC, and that is really needed as well. And that was my problem with Dyendas. Sure I could survive fairly well, but not anywhere near a clerics survivability. Sure I had more offensive, but I had to dress properly to get it. Then when I would think about it, I just couldn't put a perfect paladin suit together. Clerics just would always come out the logical choice, as they don't have to mix and match their equipment as much. They dont' need a 'perfect suit'.
Towards the end with Caesharin I did very very well with the way I suited up, especially considering my limited EQ knowledge. My standard suit had me about 40 to 45 hit/dam with somewhat low saves. I then had some other pieces in my inventory that I'd remove, and it would give me about 35 hit/dam but I'd have (including the -svs) around -50mal/-50aff or so. My mental was lacking, but, for clerics, I found that having at least half-way decent mal/aff saves was much better than having the mental saves. Why? Because Minister lands fairly often. So you have to sacrifice an awful lot in terms of other saves/hit/dam for brilliant mental saves to have any affect on minister not landing. And many have said, even with top-end mental saves, it would eventually land. By having at least half-way decent mal/aff saves, you will get ministered much easier, BUT, you are effectively cutting down on what they can do to you when you're ministered (aff saves VS path, mal saves VS mals from path).
Now that suit switch worked for me, and the saves suit worked againts mages most of the time (A couple of non-rare vsmal in a sack would help to boost that -50 mal a bit further against shaman). The only problem I had there was a lack of good mental saves against other classes, but, that will come with exploration for me. Now with better aff/mal saves in the mage suit it would help even better against those nasty cleric types.
In a nutshell, I found that going svmental against cleric didn't help much because minister would eventually land anyway, and then you'd be a little more vulnerable to what they can do actually physically harm you.
Dey
As far as paladins and flail, I say nay. Paladins are already strong enough. They need no more offense, or defense (yes, defense).
I was referring to rare flails.