This is the correct answer. It even punishes you for not being stealthy, but stealthiness=insta-kill.

Hitman: Blood Money and Manhunt

Knives or so 80's Chainsaws on the other hand........Madworld is your friend:p

play velvet assassin.

Play MSG4: Online is not sold seperately and is part of the game. But to be honest the single-palayer is so over-whelming that I have not got to the online part yet :)

In MGS4 you can take the sneaky approach and stick knives or syringes into people if you chose to. You can also blast them out with weapons, or voodoo doll them into destruction :)

in MGS4 you can sneak up behind ppl and do a variety of different things: hold them at gunpoint and have them empty themselves of ammo, etc.; choke them out; grab them around the neck and drag them/use them as human shield while u shoot at other enemies; or u can choose to just take ur knife and slice their throat. I think there are other options, but that's all i remember right now. U GOTTA check out MGS4, best game ive ever played alongside Uncharted 2.

Someone mentioned Uncharted 2...i think everyone and their mother MUST at least try Uncharted 2 just bc its an incredible game. As far as the stealth kills though, ur not violently stabbing ppl in the back; the stealth kills are all done via melee..u can take someone out around a corner in a variety of different ways; u can sneak up behind someone and jump on their back and break their neck; u can take someone out behind cover-grab them by their shirt, drag them ontop of ur cover, elbow them in the throat/chest, then drag them unconscious behind ur cover with u; and lastly u can pull someone off a ledge while ur hanging from it. This games great, and the stealth kills are an added bonus to an already amazing game. Oh yeah, and the multiplayer is ridiculous amounts of fun, the first game to get me into online multiplayer...

Oh yeah, and one last thing...someone also said Uncharted 1 had stealth kills. While I think u should still check out U1 bc its a good game, i don't want u to be misinformed. U2 is the first game in the series to have stealth kills.

Try Arkham Asylum.
It's thoroughly amazing.

be a witch in MW2! (marathon + lightweight + commando + tactical knife) though thats not so much stealth though, its more like inspector gadget on meth shanking people...

hitmans' another game that comes to mind, though i havent played any of the recent ones (last time was ~4 years ago? probably more)

Don't play Velvet Assassin. Technically, it's what you're asking for but "technologically", that game is a mess.

MGS4 is THE game you are looking for. It is particulary satisfying to take down the enemies with the knife while keeping low profile ;)