I second the idea of asymmetrical multiplayer stealth. I've always wondered what it would be like to have a game where a player operates a large set of security cameras and merely viewed them all through the monitors. As long as the guardsmen players could only remain on a central location of the map, I'd imagine a good part of the game's tension would be just having the assailant wait safely on the far edges of the map, as if being picky about opportunity. (Then again, asymmetrical multiplayer is a genre I've always been interested in.)
When it comes to stealth, I have a rather strange history with it. A while back I was invited to join in the games on a Halo: Custom Edition server with some friends. At that point I hadn't even played an FPS in a few years, and I had never played Halo before. So not only was I incompetent, I was also on a bad connection: where my bullets only hit the other players two to three seconds after I thought they should. This led to a strange phenomenon where I could be packing six frags, ten rockets, invisibility, and fully powered shields, yet still be somehow a sitting duck.
So I ran away like a coward. A lot. I tried being a camper with a sniper rifle, but my aim was too off, and I usually always gave away my location just by even existing on the server anyway. So one day, on during CTF on a relatively complex map, I just decided to try and take the most roundabout, obtuse way to the enemy camp and just swipe the flag. Thankfully, everyone else was too busy shooting at eachother to mind lil' ol' me, and to my surprise, they remained that way even while frantically on the hunt for me. This pattern repeated, and I soon earned my title as "Solid MW" for any CTF match.
However, it took a bit of getting used to, especially since the game of Halo really isn't adjusted well for stealth, especially since Master Chief's feet must remain firmly planted on the ground at all times. A lot of my practice came from planning out my routes on the same maps in solo far ahead of time. It was only through the process of general memorization and effective planning that I got a hodgepodge version of stealth to work, and even then it was only good on very complex custom maps. Continual use of Blood Gultch was always the most difficult to win with.
Stealth games are kind of like really actionful puzzle games in a sense -- just like the Castle Courtyard in Zelda 64, only instead of just being thrown out to try again, failure gets you savaged by a pack of mad hounds. Maps and levels usually have a very singular way of beating them, and the real experience of the game only comes from the first time playing it, and after that their continued success at the game is only bolstered by the fact that they are too familiar with the enemy environment already. They see the puzzle already knowing its most optimal solution. This makes me wonder if a procedurally generated stealth game, or even a stealth rougelike, would even be possible for a player to complete.
You know, I actually kind of figured a way to use bad guard AI to my advantage. Once I made a stealth joke game which was a continuation of my Halo CE history. While it never got past alpha with one complete level, it had a lot of stuff of the standard stealth genre. Yet, the most fun and enjoyable part of the game were definitely the banana peels.
The banana peels actually took the guard's easily exploitable patterns and actually made it a strangely satisfying gameplay goal. For some deep, intellectually primal reason, seeing the dumb guards literally fall for it just never got old. I'd love to make an entire game out of just stealth and bananas. Seriously.