I remember, back in those halcyon SNES days, I played Super Mario World like mad, and somehow got to the Special World on my own without a walkthrough. I remember getting to Tubular (which is the most difficult level in the game), and being so angry that I could never complete that I'd often throw my controller on the floor. Fast-forward many years later, and I found that you could use a Blue Yoshi to pass the level. I reloaded the game in a ROM, played through as small Mario with a blue Yoshi, swallowed a Koopa and won on my first try. It probably should have been satisfying, but I felt like a chump.
Also, the final boss battle in the original Deus Ex. The first 98% of the game is some of the best FPS/RPG gaming of all time, but the lackluster way you get the endings aren't up to snuff. I remember turning on the final generator to stop Bob Page, while a melee was going on between a security bot and genetically-engineered creatures behind me, watching Page blow up like a fool, and thinking, "This should be awesome, but it really isn't". Same goes for the final boss in Human Revolution - I still had a plasma rifle with me, and decided to shoot it through the glass at her on a lark. I won the game in twenty seconds.