Personally, the one thing that makes or breaks stealth games for me is "freedom." First, I want to be free to screw up and be able to recover. None of this "you get seen, instant game over" crap. One of the reasons Thief 1 and 2 are so much fun is actually that the AI was utterly retarded, giving you ample time to recover from mistakes. Second, I find stealth a lot more satisfying when I feel like I'm free to figure things out for myself, and not just trying to figure out the one workable path by trial and error. Again, I'll turn back to the original Thief games. Another reason they are fun is that they are incredibly open, giving you freedom to explore large levels pretty much as you please as well as the freedom to deal with enemies in a variety of ways via a variety of paths.

In contrast, one of the reasons I found the stealth in Escape from Butcher Bay to be relatively unsatisfying is that it was both extremely sensitive (you get seen, you reload your save), and extremely linear (there's rarely more than one correct way to progress). So it was just a lot of trial and error as you tried to deduce what that one correct path was, constantly getting spotted and having to start over.

That's my two cents at least. Basically, just do what the first two Thief games did :)