1) Solomon's Key

Without using the continue cheat, or looking up solutions to this game's puzzles, this game is hard, as in maybe you can beat it after playing an hour a day for two years. Individually, the later rooms take dozens of tries each in order for the player to decipher a winning strategy, but the player has just a few lives to clear the entire game, and just getting back to the room you were stuck on after losing all of your lives is a major achievement.

2) Ikaruga

I could have chosen Giga Wing or Strikers 1945 plus, or a bunch of other games for this slot. Basically, any arcade shooter with a continue feature will be absurdly difficult to try and beat without excessive continuing. I'm not going to bother naming coin-munchers like Rampage, which are impossible to beat without continuing. But the possibility of clearing Ikaruga in one play, if you use perfect maneuvering and timing, makes the challenge of trying to do so highly addictive.

3) Mike Tyson's Punch Out

Or Mr. Dream's punch out. Both Tyson and dream are not only super-hard final bosses, but they cannot be repeatedly challenged without replaying earlier fights.

4) Legacy of the Wizard

Figuring out where to go in this game without a guide isn't impossible, but it takes a long time, and lots of experimentation. Plus, once you figure out where to go with each character, you must still make long trips full of dungeon-crawling with no save points, and limited ammo for destroying monsters.

There's a zillion games I remember getting stuck on as a kid, but most of them I can easily beat by now. Some examples are the last three levels of Ninja Gaiden, the Conquest mode of Populous for SNES, Cleopatra in Double Dragon 3 for nes, etc. But if you watch a master player of Solomon's Key or Ikaruga, it's like watching a master pianist. What they're doing seems possible, but there's absolutely no sense of "gimme the controls, I can do that."