There are objectives like that in Crysis 1, at least. It is just left up to you whether you want to accomplish them by stealth or force. Are you after games where you are restricted to completing the objectives in a specific way?

And the difference between "find hidden papers" and "flip switch B" is in the wording only. You find the object, you push some sort of action button, objective completed.

What about Hitman? Although that is TPS, not FPS. Of course, there you mostly also get to decide for yourself how you want to complete your objective, and again, the objective is basically "kill X". Still, the gameplay is usually more varied than just going in with guns blazing.

Perhaps. NOLF made me feel like I was doing a lot more than shooting dudes and flipping switches. Even if that was a trick of presentation I haven't felt that way in a long time.

Would you consider L.A. Noire - Not really a shooter however.

or

Possably Mirror's Edge

Closest I can think of is Deus Ex: Human Revolution.

Come to think of it, the Goldeneye remakes were of similar vein as well.

Arma 2 has objectives that are both optional and failable (word?). Does that count? Goodness knows you need a lot of stealth to be successful as well...

You're including "multiple ways to accomplish the objective" right? I guess one could loosely call Deus Ex: HR a shooter, but it's not in the sense you mean.

And on the other side, Halo 4 definitely has that, but doesn't have a lot of ways to do the task, though if you play on Legendary at all, you'll get pretty fucking creative at times.

Arma 2 has one of the best, well thought of SP parts I've seen in any game. It's a shame that it got so little attention.

What about pinball? Somehow I think this genre should be listed here - unfortunately.

I was thinking complex business simulations are dead, but oh well, some certain type of special fps subgenre is ok,too.

Great, and now I feel old. I also realised why I stopped playing FPS games, I played all 3 examples you list but don't play any nowadays.

What's the difference between "kill person X, pull the switch Y" and "find the papers" ?

But we do need more shooters like NOLF, because pretty much everything right now is a COD or COD clone.

PS. I want Vietcong on GOG.

I'm afraid unless somebody writes "NOLF 3" in here the OP won't be satisfied :)

but I don't blame him, there (unfortunately) isn't anything remotely as cool as NOLF now...

I must admit, this "objective based" factor is something that hasn't really occurred to me yet. I mean, of course I know that the "real FPS" games of these days are more linear than lots of titles ranging form the mid-90s to early 2002s, that the search for keycards is gone forever, secret areas (especially the ones involving easter eggs) have become rarity but dang, indeed, it's been ages since I had to press TAB or F1 in an FPS in order to remind myself of what I actually have to do (the newest one I remember is probably Crysis).

But I've gotta say, there's probably reasons why nobody does that anymore. Just think of Jedi Knight where finding the one right way and all those keys and switches was such a big challenge that you'd spend lots of time traversing the same enemy-free areas over and over again. I guess most designers have come to the conclusion that this kind of gameplay is not the right choice for an FPS where the core mechanic is shooting targets. Those objectives usually involved solving logical puzzles or challenges based on navigation, these days there's actually even hardcore shooters without the ability to jump.

Makes me think... space sims like Wing Commander and Tie-Fighter had heavily objective-based gameplay which mostly involved proper use of the simple movement and combat abilities. How is it that the only shooters that implement this stuff these days are tactical shooter and simulators like ARMA? Then again - these days the average gamer pisses his pants in anger when he has to escort an NPC for two minutes. Guess those stupid kids are the problem.

I agree. I was very surprised when I first played it, completely not what I expected. Too bad the engine sucks :\