I dont think any of the 2600 games I had could be "beaten". Likewise, several early NES games like Kung Fu simply restarted from the beginning.
No, the first game I remember beating was the original The Legend of Zelda. It took several months to work my way through that geme; even with checking the overworld map in Nintendo Power. I was so pleased with myself when I finally beat Gannon. Who knew there was a whole 'nother quest after that (of course you could just skip to the 2nd quest with the character name "Zelda"). Funny thing though, I never *did* find my way into the right eye on the Death Mountain underworld, so I never got the red ring (though I have gotten the red ring on my 360 *rimshot*).
Gamer Confession: I have never beaten SMB1. Even with all the lives from the stairway-shell trick, I just couldnt do it.