Super Ghouls 'n' Ghosts for SNES took me an entire summer to beat... such an unnecessarily frustrating game. After you get through all the levels the first time, you have to play through the game AGAIN, only this time you have to pick up a special (bad) weapon along the way and beat the final boss. You also don't get to save, so you have to play through the whole thing in one sitting.
Yo! Noid and Back to the Future for NES were also insanely difficult/terrible.
Ghouls n' Ghost definitly.... this is the one game that made me toss controllers in anger more than any other.... Good call!!!