Just taking the Shadow Creature template from Lords of Madness seems to get you what you want; it's the beefed up version of the dark template, and one of the options is fast healing 2. +2 LA, and it also gets you Cold resist 5+HD (max 15), total concealment at all times except under full natural daylight and daylight, and +6 racial mod to move silently. You also get +50% speed, and increasing abilities as you gain HD (plane shift to/from Plane of Shadow 1/day, DR 5/magic, +2 luck bonus to all saves, evasion, fast healing 2, Mirror Image 1/day.)
Does the Dark template give you a bonus to hide? I guess I find it odd that one is supposed to be a weaker version of the other, but they might give bonuses to different skills...