The rules
Critical hit immunity confers immunity to steal spell
Sneak Attack (Ex): […] See the rogue class feature, page 50 of the Player’s Handbook. […]
(Complete Adventurer pg. 16)
Sneak Attack (Ex): […] A rogue can sneak attack only living creatures with discernible anatomies—undead, constructs, oozes, plants, and incorporeal creatures lack vital areas to attack. Any creature that is immune to critical hits is not vulnerable to sneak attacks. […]
(Player’s Handbook pg. 50)
Here we can see that you cannot sneak attack creatures like this at all—they aren’t merely immune to the extra damage from sneak attack, but they aren’t valid targets for it in the first place.
Meanwhile,
Steal Spell (Su): […] A spellthief who hits an opponent with a successful sneak attack can choose to forgo dealing 1d6 points of sneak attack damage and instead steal a spell, or the potential to cast a specific known spell, from his target. […]
(Complete Adventurer pg. 16)
This says you have to perform a sneak attack—which you can’t do to one of these creatures—and moreover, you have to actually have 1d6 points of sneak attack damage to give up in order to use the ability.
Note that the next line, “If the target is willing, a spellthief can steal a spell with a touch as a standard action,” doesn’t involve sneak attack. You can borrow a spell from a willing undead spellcaster or whatever.
Fortification uses different wording—but still blocks spelltheft
Fortification […] When a critical hit or sneak attack is scored on the wearer, there is a chance that the critical hit or sneak attack is negated and damage is instead rolled normally.
(Dungeon Master’s Guide pg. 219)
Negating the sneak attack means you did not “hit an opponent with a successful sneak attack,” and also that you do not have “1d6 points of sneak attack damage” to “forgo.” So fortification also blocks steal spell.
In practice: DMs should houserule this
Spellthieves are a weak class. There is no reason for them to not be able to use their signature class feature against a wide variety of otherwise-valid targets—the fact that they need spellcaster targets in the first place makes them extremely niche to begin with, adding more restrictions on top is just unnecessary. They don’t really deserve to lose 1d6 damage when they do it, either, but if you really want to keep that then it’s fine to just understand that you’re sacrificing a hypothetical d6 even if none of them would apply.
Actually, for that matter, they should also just apply more. The rogue is a weak class too. Pathfinder dramatically scaled back immunity to sneak attack—and the Pathfinder rogue is still a weak class. And you can get sneak attack on every single attack roll you ever make—and still do vastly less damage than the barbarian or fighter.
But if you need something official...
Official Solutions
Some claim Dragonfire Strike gets around this, but probably not
Dragonfire Strike is a feat from Dragon Magic that says
Benefit: When you gain extra damage from a sneak arrack, sudden strike, or skirmish, you can choose for the extra damage to be fire damage. If you apply this effect, increase the extra damage dealt by ld6 points. Make this choice for each attack after it is resolved bur before damage is dealt. This is a supernatural ability.
(Dragon Magic pg. 18)
Some argue that this allows you to sneak attack things that are immune to regular sneak attack, because it’s no longer precision damage but instead some special mystical dragonfire attack somehow. The problem is that, as we just established, attacking such a creature is never going to trigger “When you gain extra damage from a sneak attack,” because you aren’t able to sneak attack such targets and don’t get extra damage.
Penetrating Strike definitely works, but is too costly
Benefit: Whenever you flank a creature that is immune to extra damage from sneak attacks, you still deal extra damage equal to half your normal sneak attack dice. This benefit does not apply against creatures that cannot be flanked, nor against foes that are denied their Dexterity bonus to AC or flat-footed but not flanked.
(Dungeonscape pg. 13)
With this alternate class feature, you can still deal at least that “1d6 points of sneak attack damage,” and therefore steal a spell, from creatures otherwise immune (unless they’re also immune to flanking).
Problem is, this alternative class feature replaces the trap sense of a 3rd-level rogue—meaning you need three levels of rogue to get it. That’s three levels that don’t count towards your spell stealing, which is monumentally painful.
Wands of golem strike, grave strike, and vine strike are probably your best bet
Spell Compendium has a set of three 1st-level swift-action spells, golem strike (pg. 106-7), grave strike (pg. 107), and vine strike (pg. 230), that allow you to sneak attack constructs, undead, and plants, respectively. Spellthieves are Charisma-based and have Use Magic Device in-class—you should definitely feel comfortable activating a lot of wands.
Putting the wands in wand chambers (Dungeonscape pg. 34) built into boot blades, knee blades, and/or sleeve blades (Complete Scoundrel pg. 109) will keep them always accessible.
All told, this is pricey—the wand chambers cost 150 gp each, and have to be built into weapons that have some cost of their own, and then the wands are 750 gp each and may eventually run out. But it’s actually worse than that.
First,
As a rule of thumb, weapons cannot have modifications unless they have a solid hilt or handle that is at least 6 inches in length.
(Dungeonscape pg. 33)
One might suspect that the hidden weapons in Complete Scoundrel would not meet this requirement, and indeed, we don’t have strong, clear description of any of them that includes or even suggests a handle. However, the descriptions of boot and sleeve blades say to “Treat [them] as a dagger,” and the knee blade says “Treat a knee blade as a short sword,” and daggers and short swords at least can have a handle of that length (though it would be weird). So maybe ask your DM really politely.
Second,
Activating a spell trigger item is a standard action
(Dungeon Master’s Guide pg. 213)
Wands use the spell trigger activation method, so casting a spell from a wand is usually a standard action
(Dungeon Master’s Guide pg. 245)
Activating a spell trigger item takes the same amount of time as the casting time of the spell that the item stores
(Rules Compendium pg. 85)
See here for the lengthy controversy about Rules Compendium vs. the core books, but suffice to say, some DMs don’t buy Rules Compendium here, treating this entry (and similar others) as an error, and using the rules in Dungeon Master’s Guide (and other core books).
In the specific case of wands, however, we do have some wiggle room: wands are said to “usually” take a standard action to cast. That’s certainly true of spells, most of them take a standard action. The rules for spell trigger items don’t really offer that much flexibility, but wands could be a specific special case.
Anyway, assuming you can get them in wand chambers and thus available, and you can activate them as a swift-action, these wands are almost certainly your best bet. Even without the hidden weapon wand chambers, Quick Draw isn’t a terrible feat for a spellthief and might be a good solution here.
Of course, these wands only cover constructs, undead, and plants. Oozes, anyone with fortification, or various random other critical-hit-immune creatures won’t be subject to these. Incorporeal foes are arguably vulnerable if you have ghost touch and they lack other sources of crit immunity, but that’s not entirely clear—and the existence of the ghost strike weapon property in Magic Item Compendium (pg. 35) that explicitly handles this at a much greater cost might ruin that argument. Ghost touch plus grave strike should be no problem, at least, for incorporeal undead, which is the vast majority of incorproreal creatures.
Undead-specific: deathstrike bracers or greater truedeath crystal
Magic Item Compendium has a couple of items, deathstrike bracers (pg. 66) and greater truedeath crystal (pg. 93), that enable sneak attacks against undead targets. Undead spellcasters are by far the most likely problematic targets for steal spell, seeing as they are very common while constructs rarely cast spells and oozes and plants are fairly rare in any capacity (and those that cast spells are a minuscule fraction of those).
