Interesting dilemma. At what point does 'Hard' become 'Unfair'? Depends greatly on the genre, but FPS shooters allow for the most common analogy- if you die due to an ambush, or something you could have prevented, it's fair game. If you die suddenly with no warning at all due to glitches or crazy-farsighted snipers you can't see (Farcry), it's unfair.
Basically, if there's a way around an obstacle that doesn't involve blind luck or something no one would ever guess without a FAQ, it's fair. There's only a few games I've ever played where I felt it was too hard for it's own good. One that comes to mind is the mission in the first Rainbow Six (Glass Tiger?) where any detection or deaths means a mission failure. There are two floors accessible from the rooftop starting point- one takes you right into a sniperfest extravaganza in the main lobby (for the guards, not you) and the other one opens into an elegant hallway with one patrolling guard. This is the only way in. You basically have to make a guess when the guard is in the hall since the shaft metal prevents you from hearing his footfalls. One try in four, you'll make it across the hall to the next room without being seen if you run... That makes one down, another 5 or so close shaves like that to go. Fun?
Limited by technology as older games were, you can forgive them a certain lack of realism. In turn, more realistic games tend create a better sense of achievement if that's what you're aiming for. Strategy games are generally better at this because you have a lot more options than just one guy's weapons- no matter how many times a mission or campaign kicks your butt, there's a bunch of other ways of doing it you haven't tried yet. Warcraft 3's Frozen Throne Campaigns are legendary for their difficulty on Hard mode, but with the sole exception of the final mission, trial and error won the day for me.
At the risk of repeating material from my last post, I thought Advance Wars: Days of Ruin's last mission to be the unfair kind of Hard. There's tons of walkthroughs available and I did eventually win, but every single guide referred to a certain point where you would build high-priority units (usually Medium Tanks) at a far off area to glitch the AI into Mortaring them instead of your main force. That would be like finding that the last boss in a NG/DMC/GoW style action game will sit perfectly still and let you kill it the entire battle if you walk around in a circle 3 times and slash at thin air. If you have to exploit the AI via nonsensical moves to win, it's the broken kind of Hard.