The healing magic formula needs to be reworked, nobody can doubt that. And "Just give RDM Cure V" doesn't even begin to address to problem. But lowering the power of cures is something they have to be REALLY careful of, lest you get a lv 41 WHM being unable to heal a lv 41 party. Or even poor SMN, who is forever forced to play from their sub due to their ridiculous timers.

I'd say keep the base cure potency on each spell the same but alter the amount given by healing magic such that all spells get much stronger (even Cure V) with higher healing magic. Go a step further and give WHM a JT that whenever they cure someone there is a chance of a debuff being removed based on healing magic skill. And / Or Erase II that removes multiple debuffs based on healing magic skill.