My personal problem (if problem is the right thing to call it) with this is that, assuming the tension is truly founded due to the randomness and the unreliable nature of the patterns, then you're right that it's not a challenge. But it is luck.
Does the random element truly have a place in stealth games? If I do everything perfectly and still get caught, I'm going to feel a bit robbed. Left to either savescum (in which case the random element is a design failure) or shoot them.
IMHO you lack context: "twitchy" enemies usually have long patrol routes, they turn around once per round and the areas they peek at are small places between to pieces of cover. It wouldn't be a huge deal, though I guess it would be boring in the end, having to wait for the turnaround just to continue. But stealth games are about waiting anyway.
Garrett used a bit of Keeper magic to do that actually.
Unlike, say, FPSs, there is something to talk about. Most stealth games use very different mechanics. AC (2 at least), Batman: AA, MGS, Thief, SC, SC: Conviction, DX:HR all have different rules and stealth AIs.