Along with that Leo-J try and beat Hudson's Adventure Island I, II, and III for the NES; I was only able to beat the first one, and that only after trying the game about ten years later after I failed and then picked the game back up again.

Try also Blaster Master (NES), Viewtiful Joe (Gamecube) beating it on all difficulties.  Meag Man without using the cheat to beat bosses and Rockman.

For real kicks see if you can locate Star Control II for P.C. and beat that without any kind of guide or walkthrough. 

Beat Killer Instinct on the hardest difficulty, Double Dragon (orinigial one for the NES), just to name a few more. 

Surely there are some games that you have played and not been able to beat, or perhaps you are playing some really sissy games like Smurfs for Colleco, or perhaps you are getting your game on with Power Puff Girls, and other Nick Jr. cartoon games.

For me the hardest game of all times is Beatmania Distorted... It doesn't matter how many credits I spend on this arcade, I always fail((

The Muppets game for the NES. Jesus Christ almighty, that game was a nightmare!!

I say Batteltoads for NES

Yeah that was a tough game... the bosses drove me to the edge of madness (freakin' Vergil!) I was able to beat it on normal, but what a struggle. I started Hard mode but haven't taken the time to get far into it, so I don't know how far I can get on Hard. I tend to be persistent, though, so it'd just be a matter of time. The first Devil May Cry was killer too... beat that on normal.

I'm playing God of War 2 on Hard and making serious headway; it's tough, but just tough enough to be worth my time. If that type of game isn't difficult (fast-paced combat-oriented), it isn't worth playing.

I beat Viewtiful Joe on normal; I remember that being one hell of a game... quite a test of talent. That's how I likes 'em.

Edit - Oh, and I recently beat Mega Man 7 (SNES) on an emulator... Geez, I did not expect the game to be that tough. If it wasn't for the save-state feature of the emulator I probably would have said "screw this," since the story wasn't terribly compelling and I was just sorta casually checking the game out when I started it. I was fine for the most part, until the Wily stages...

There's a lot of NES games I played to death without ever coming close to finishing them : Castlevanias, Double Dragons, TMNT. But I'm quite proud of the fact that I did beat Battletoads (once) without using any warp zones, the only trick I used was getting 1ups by hitting the birds in the second stage multiple times (but that's not a cheat)

Legend Of Zelda: Ocarina of Time. That phantom/zombie temple is crazy and I though the water temple was crazy! :(

Been trying to beat Adventures of Lolo 3 for many years

Mega Man X ..........

Ninja Gaiden for Xbox that was difficult on easy the new NGS for PS3 is alot easier than the original.Took me awhile to beat DarthMalek at the end of KOTOR1,KOTOR2 was easy though.Onimusha3 on critical mode that is a joke cant even get past the first boss because you can only kill enemies with critical attcks which are a pain to time right.I havent finished FFXII but thats because i got bored of it not because its hard its actually really easy for me.FFIIIDS is a pain without a guide there is no clues on where to go next unless you talk to EVERYONE and i mean EVERYONE.