So you're suggesting something like:
Physical Immunity (flavored as instant regeneration)-8
Stacked Catch (Decapitation: attacks to the head and neck that can feasibly remove it, all heads must be decapitated, easily researchable)+4
[Notes: The catch is +2 because it is very easy to find out that you can cut off a Hydra's head. Nearly all of the lore of the monster relates to it. Attacks that can feasibly remove a head are quite common: cutting, burning, slashing, automatic weapons, acid, etc. so another +2 Theoretically, a GM could rule that you'd have to be aiming at the head and neck for this to work, requiring a maneuver and reducing this to a total of +3 or even +2, but as a GM I wouldn't require the maneuver so I'll leave it at +4.]
Hydra's Regeneration: [-8]
Musts: You must attach a Catch to this power.
Description: Whenever you lose your head, you grow two more.
Effects:
They Keep Coming Back: Whenever an attack deals enough stress to take you out, your head is removed. At the beginning of your next turn you grow two new heads as a supplemental action unless this power's catch is satisfied before.
Two Heads are Better than One: You gain an additional stress box for each head you have.
Catch (Fire/cauterization, easily researchable)+4
[Notes: This power is based on Physical Immunity, so I gave it the -8 refresh. Basically, if you're taken out you gain more stress making you effectively immune to damage. The catch is very easy to weaponize and easy to research, making it a +4.]
So, essentially, the total cost of the Hydra's regenerative powers (Physical Immunity plus Hydra's Regeneration) with all of the catches is the same as Physical Immunity with a +0 catch, which I think is fair.