Adventure Island on the NES.
Anyone who says anything else has never played Adventure Island. I tried to beat the game with my cousin and brother. We even used the unlimited lives cheat and, after about 20 hours of playing, 4 hours of which were on the second to last level, we gave up. And this isn't something we did when we were uncoordinated children. We broke out the NES for nostalgia over Christmas weekend when we were all in our prime (ages 18-25). We realized that, if you die once preceding the last level we got to, you lose your ability to throw fire, and there's no way to beat the level without it and no way to get that ability back.
Also, I don't think that any game that has saves or checkpoints can be considered hardest game of all time. You know what's hard? Going through hours of playing on an old-school platformer, only to lose your last life to a simple mistake. Do you get to start over from the beginning of the level or from the last checkpoint? Nope. Try the beginning of the game.
Not only does this mean that to get through the game you have to have a constant stream of near-flawless play, but increases any frustration factor because, aside from a possible high score, you start from the very same place and with no other advantages than you did hours ago.