I didn't have an original NES until 1998. I had it for about a year before I bought the Pod Racer edition N64. During that time I didn't beat ANY of the games I got with it except for Tecmo Super Bowl...the best football game on that system. Took the Packers to the Super Bowl twice with perfect records.

Anyways, I have a number of coughromscough on the PC, and I've beaten most of them. All 6 Mega Mans. 3 Marios. Kirby's Adventure. Chip and Dales Rescue Rangers.
I've only beat them, though, because I had the ability to save-state with them.

I haven't beat Ninja Gaiden, but then for some reason I'm not to fond of the game.