It's a big stretch on the definition, but try the Hitman Trilogy. There are tons and tons of solutions to achieve the kills without trying for tricksy, difficult stealth challenges - just by recalling a bunch of hints you've seen/heard by wandering around the region, and combining them in fun ways.

Basically, if you see that the target is inside a complex guarded by two armed men, you shouldn't be trying to flick a coin to see if you can turn a guard just long enough to use your garrot on one, and hide him around a corner, all in 10 seconds. You SHOULD, instead, look for options like:

• Find a pizza delivery guy, get him alone, knock him out, take his uniform and pizza, and greet the guards so they let you in
• Set off an alarm in a nearby room that causes a guard to go shut it off
• Call the target on the phone and tell him you want to meet about his secrets. Then, he leaves the complex himself with one bodyguard to your proposed meeting spot "right underneath the suspended ornamental anchor".

What's often misleading about the games is they orient themselves around all this equipment you can bring in, but the best way to explore a lot of levels is with no equipment at all (sometimes not even a pistol). Granted, the game changes in speedruns and other challenges, but it DOES feel like playing a Monkey Island game at times.