Nah, even tiefers have a cerebral-spinal fluid and a skeletal nervous system. Plus, their body chemistry still would be affected by snake venom, ooze enzymes and the like. Their immunities to other sorts of spells are primarily to reflect their strangely evolved planar minds as the spells like hold person were written on this normal plane with typical humanoids as research subjects. Dominate, Charm and Hold Person are all enchantments which must target the mind. Paralyzing on the other hand can take many forms; physical, chemical, being forcibly held by a Bigby's, etc.
Hold Monster works on them since it's better than hold person in that it affects a much wider range of targets with a wildly different physiology range.
Now I'm not exactly certain what keeps Deep Dwarves immune from all paralyzation... but I would theorize that perhaps their skeletal nervous system in more closely guarded and that their bonus vs poisons helps them resist enzymes and paralytic poisons of all kinds. Eons of living with oozes as pets, battling driders and getting clocked in the head by Deep Giants can do that to a man. Still, you could Bigby's them with an external force of sorts.
OH! And while we're on the topic, I remember Grovel and a mage lass were experimenting with her hold person spell and we found some limitations that didn't quite fit right. Some creature types are immune to Hold Person who really shouldn't be, like all non-stock NWN humanoids. This includes NPC giant-kin like ogrillons and half-giants, NPC orcs, NPC goblinoids (but not PC ones, as they are halflings or half-orcs with skins). This results in Hold person being able to affect PC Orcs, Half-orcs, Half-Giants, Half-Ogres and Goblins, but not the NPC variations. Mechanically dubious, as they are both IC the same races.
NWN only considers Humans, Elves, Gnomes Halflings, Dwarves, Half-Elves and Half-Orcs as humanoids, and all playable subraces as the base race is recognized in preference over the added skins. According to PnP, These are the classifications of Humanoids.
http://en.wikipedia.org/wiki/Humanoid_(Dungeons_%26_Dragons)
Note that they have changed classifications between the editions. In my opinion, humanoid would refer to anything with 2 legs, 2 arms, head, torso and abdomen that isn't otherwise undead, aberrational or immortally planar. A human, elf, orc, kobold, lizardman, githzeri etc. would be humanoid, but not a celestial, demon, lich, Ethereal Filcher, Shadow, zombie, Dragon or Mindflayer would not be. (they have tadpole stages and usurp & bioform humanoid bodies parasitically). Things like Centaurs and Wemics and Half-Giants? That'd be a tough one. I think the centaurs and Wemics might be considered humanoid while half-dragons would be composite creatures and fall under draconic families. When a Red Dragon Disciple gains half-dragon form, they get some funky immunities.
