Depends on the type of game really. Some elements are universal, but I think the type of game (first person, third person, top-down, etc.) control some of the elements. I mean you have Rainbow Six back in the day where if you were spotted once during a stealth mission you failed, or SOCOM where stealth made missions easier, but getting spotted had you swamped with enemies, and then there is Metal Gear (which for a fan of the series, like me, is better to just experience the game rather than reading reviews of it).

I'm not really seeing what the point of the enemies are if you are making the player solve puzzles, but avoid the enemies. At that rate you might as well drop the enemies and stealth and go full puzzle game. I suppose you could incorporate it so that if a player messes up a puzzle they have to fight. Stealth games usually do have a mix of action and stealth. Using my examples above, Rainbow Six had two or three stealth missions from what I remember and the rest were designed for you to send your team in and clear the area. SOCOM allowed you to do stealth like missions or you could run in and start shooting the enemies. MGS has a ranking system that motivated you to use stealth by giving you perks (titles, items, etc.) for the stealthier you were.

For me, the first rule of making a video game is to make something that you will like. So I guess the real question is, What do you think should be in the game?

I'd personally read up on literature and play games that utilize the stealth element. Also, 'lock picking' can generally be seen as a small puzzle such as in Thief 3 or Skyrim.

Also, what elements in your game would be unique? Or rather, whats the scale of proposed unique features? How do you experience it?

Actually, The Witcher has those elements, can't miss a triple A title like that ;)

The big things for me, is that stealth games need to be very clear as to whether I am hidden or not, and what an enemy can see. Gameplay over realism every time in this regard, it's better to have a Light Meter or draw the vision cones of enemies than it is to be frustrated by being spotted by enemies that I didn't think could see me, especially when I thought I was hidden. Often times making the enemies extra 'stupid' actually makes the game play better, for example, if you run into the view cone for a very short period of time, like less than a second, have the enemy do a, "Huh, what was that", as opposed to "ALARM ALARM ALARM". Another example is limited view range on enemies, especially in 2d games, it's incredibly frustrating to be spotted by an enemy that is across the map, or not even on the screen.

The AI has to be really consistent as well, a stealth game where an AI will have a bug where they occasionally spot players through walls (hello Tenchi series), isn't going to be played for very long.

Another big one is the fail on being spotted and being forced to restart an entire sequence, losing anything over just a minute or two of gameplay time due to being spotted is a dealbreaker.

Try to avoid a confusing combination though (ala Metal Gear Rising Revengeance). According to the trophies and titles you can stealth your way through most of the game, but I've yet to see how as you usually end up in a battle in almost every turn. MGRR seems like it doesn't know if it wants to be a button masher or a steal espionage game like its predecessors. There is definitely a fine balance that has to be met or it feels forced like in that game as the only stealth you have is running behind an enemy and pray they don't turn around to see you. Finding that balance, in my opinion, is one of the fun challenges that makes game development fun.

Freedom of choice and experimentation :

I believe the mechanics should not conflict each other but rather intertwine. If you have one mechanic in which you can sneak without firing a single shot, and one in which one shot leaves you exposed for the rest of the game, then those mechanics conflict. An example of when the mechanics intertwine would be: firing a shot may alert nearby enemies into checking out the spot of the shot, leaving their original posts, helping the player move on by sneaking past them. The player can use his imagination to search for a way to use all of his tools at his disposal to pass a level.

Easy to understand mechanics:

For a player to be able to experiment with combining mechanics, they have to be clear. Invisibility in the shadows, noisy weapons, line of sight, dog smell, any mechanic must be clear and easy to get.

Hard combat:
Upfront combat must be hard and punishing if you want to make a stealth game. I'm not saying no to stealth kills; I'm saying no to all-rambo-gunz-blazing-kills. There's just no sense trying to sneak past 10 guards when you can just rambo them all.

Good story:

Might be surprising to hear but gamers tend to pay more attention to story in stealth games than other FPS/puzzle games, even with games like Hitman:Contracts where story wasn't in the first plane, gamers would read the whole mission briefings religiously to try and get the overall story.

Kewl Central character:

Since most stealth games are centered around one individual the player gets to play as (Agent 47; Solid Snake; The marked Ninja; Sam Fisher) that guy has to be cool. Misterious, cool, steady, badass, torn, complicated. We love those characters and making them really cool helps the game alot.

Reference Games:

Games to reference. Might be a no-brainer, but some you may not know, and they're all worth a look: Hitman Absolution (or Blood Money); Splinter cell(any); Mark of the Ninja ( this one is good mechanics and 2D stealth game to reference); Metal Gear Solid (although not a personal favorite)