Someone actually beat Tetris in the NES earlier this year. I mean beat, as in into submission. They got far enough that the game couldn't handle the progression anymore and crashed.
Which definitely qualifies it for the hardest game. All of the other games everyone is taking about have been beaten multiple times by multiple people. Tetris has been beaten once by one person after almost 50 years.
The version I played stopped after level 15. Not sure if it was supposed to happen, I only managed to get that high once. But I contend that I beat the game.