Man--you guys start talking about this while I'm asleep, and now it looks like I don't even care about this issue (HAH! If it has to do with Jmen, I'm all over it!). The idea that the mandrake root shrieks when you dig it up is from real-world, meatspace European folklore, which gave it pretty much the same powers as a voodoo doll (it supposedly looks like a human form, if you squint just right). It was believed to grow wherever a man had been hanged, which has all kinds of bizarre connotations in folklore, but none that relate to healing (as far as I can tell that's a Bungie original creation). Mandragora officiaorum, the actual plant, was used as a narcotic and a poison in Medievil times but was far too erratic in its effects (it tended to kill the people you were trying to put to sleep, and vice versa).
Here's my take on the whole thing, for which, of course, I have no evidence: before the fall of Muirthemne the root was used as an anti-agathic (anti-aging medicine) by the Guard and also as a battlefield healing agent (they had two thousand years to figure it out--they must have noticed during an idle moment or two that you could heal a stab wound with the stuff), but this was a BIG secret since it was part of their mystery rituals. In all likelihood they shared it with their Emperor and his generals (i.e., Connacht, Myrdred and Damas), which explains how they lived so long, but that was it. Only after the sack of Muirthemne and the shaming of the Heron Guard did they decide to use it to help people in general since A) there was no more Heron Guard, and therefore no Heron Guard rituals (there were no initiations during the Great War), and B) in their shame the Jmen lost all of the Heron Guard's haughty arrogance and became friends and allies of the "common" man (which is also the explanation that Bungie gives for the shovel--the weapon of the common man or some such ridiculous thing).
I think that a good session with a root would reverse the effects of aging, at least temporarily--certainly it made Alric hale and hearty sixty years after he defeated Balor. His hair became white, sure, but how many eighty year olds do you know (and this is before Geritol, mind you) who could put on full scale mail and whip Myrkridia butt with a lightning sword?
To wit, "what brings about immortality in an exceptional person" means that mandrake healing reverses aging AND heals someone of big mana (mana here just meaning "personal power", not necessarily a big blue bar that floats over your head), while "restoring the vitality of lesser men" refers to the effect it has on everyday shlubs, who only got the benefit of it after the Jmen decided they, themselves, were'nt such hot stuff if they couldn't save one city. The root could always heal, they just used to be a lot more selective about how they used it on.
Hey, a thought: maybe the mandrake plant only grows (in the Mythworld) in a place where blood has been shed in the last century or so--meaning it would have been pretty rare before the war (and the roots carefully hoarded by those in the know), but during and after it would pop up everywhere.
