The term originally came into use because many of Nintendo's early offerings were incredibly challenging to finish, including such greats as SuperMarioBrothers, Rygar, and ManyOthers. Of course, oftentimes it was possible to get so incredibly good at one of these that it was no longer hard... (ie, DanCicio and SuperMarioBrothers), but the average player would never beat the game.
I would argue that most of the original SuperMarioBrothers is not terribly difficult (especially if you abuse warp pipes). I think my personal favorite for "hardest reasonable videogame" is NinjaGaiden. The "reasonable" bit is because there are games out there that are bloody impossible to beat, but for whatever reason they're just not worth playing (e.g. poor control, crappy concept). Ninja Gaiden manages to be fun while killing you repeatedly. Even now when I play the game, having internalized just about all of the spawn points for the enemies, I still get slaughtered at a few notable points. In contrast, I can whiz through just about all of SMB without breaking a sweat (once beat the game three times in a row, in fact). -Chainmaille