If a demon has "special damage (lethal, or whatever)" defined as claws and fangs, does it fatigue them to use them, as found in the combat rules on using powers?

Yup. A very important rule. Like a couple of the other abilities, Special Damage looks better than it is.

Have a hard time with the idea that the demon has limited use of his own natural limbs, as opposed to some kind of "special" power?

"Natural limbs?" This is a demon. There is no "natural."

Demons attack using the Fists colum without buying an ability. Use that and just let the claws & fangs be special effects. That works fine for most applications; full victories are applied for temporary damage, which is extremely effective in play. Characters might also then have the Special Damage ability (and even the non-lethal option is plenty lethal at higher Power) and use it in a timed and tactical fashion during fights for the big hit. [1]