First and foremost you need to understand enmity. The cap isn't 10,000, its 20,000. 10,000 from CE and another 10,000 from VE, different abilities give you different values of each. VE goes away at 60 units per second, CE only goes away when you get hit. Provoke is exactly 1800 VE and 1 CE, at 60 CE per second it takes 30s for the hate from provoke to fade away. This is why Provoke is pretty much worthless for keeping hate, only good at spiking it at low levels.

The real issue is that the hate gain formulas greatly favor doing damage for CE and VE. Damage is worth more then Provoke, Flash and healing combined. Just imagine if every time the MNK hits the monster, its a miniature provoke and you get the idea. DD's can hit the 10K CE cap within one to two minutes, sometimes faster if they have buffs / temps. The VE hate cap is reached shortly thereafter hindered only because it's slowly bleeding away while CE isn't. Once at cap keeping hate is merely a matter of dealing enough damage that you make up for the 60VE / second loss and whatever you lose from the NM smacking you. And thus FFXI's problem is found, a MNK's fists, WAR's Great Axe or a SAM's Great Katana are better hate generators then a Paladin's Sword and all their combined abilities.

Fixing this issue would for starters require the PLD to have some sort of Enmity Bonus trait to assist in enmity generation. They would also need a trait such that enmity decays at half rate on a PLD. And finally the damage to hate formula needs to be redone, it's balanced for level 50~60 content. Until these are done a PLD will never be able to compete with a WAR / MNK / SAM / DD for hate control.