Battletoads was pretty brutal, but atleast it was comical.
Surprised Blaster Master didn't make the list, even with the cheating (pausing the game while damaging boss on... even numbered levels continuously did damage) I couldn't beat the game, it was so damn long.
I beat blaster master. Didn't cheat, but you couldn't turn off the game at night. I would leave it paused and on, until I could get back to it. I beat it a few times and eventually was able to beat the game in a single play through on a Saturday at one point. But you really had to have memorized everything about the game to do that.
I beat battletoads, ninja gaiden, castlevania, ghosts & goblins, and all the "predictable" jumping challenge games. No joke that the challenges were hard. They required precise timing and knowing what was coming. However, they were the same thing every time. If you had it memorized and had the muscle memory you could do it every time. That is how I was beating those games as a kid.
Some of the others mentioned here I beat as well. Guardian Legend I beat (actually didn't think it was that hard. I remember it only taking a few weeks to beat). I beat Festers Quest as a rental on a weekend. TMNT I beat several times. Top Gun, I'll admit I never played it. I also never played Silver Surfer. I beat all the megaman games though many times over. I also did beat the all the Contra series games WITHOUT the extra lives cheat codes. I actually managed to beat the first Contra without losing a single life. That's how much I played the shit out of that game too.
It's the ridiculous ones that were way too random in how they killed you that made you go WTF? Bayou Billy was one such game. Immortal was another one. I barely beat that one though. Ugh.
I'll admit though, I was that one kid in the neighborhood that all the other kids came to when they got stuck on a spot. I usually had beat it or could beat it. hell, I beat ninja gaiden on the first weekend I got it. It was my 10th birthday present in 1988. Beat it that weekend with a sleep over from all my friends. It really wasn't that hard except for being a jumping platformer.