Gah, so many games I can't list because I haven't actually completed them, like Battletoads and Ghosts & Goblins.
Given that I've been playing the Devil May Cry games -- the GOOD ones, anyway (i.e. not DMC2 & DmC) -- I think it's quite natural that they first come to mind. Dante Must Die in DMC3 with Turbo Mode on has to be one of the most hellish (albeit rewarding) gaming experiences ever crafted, largely due to enemies having access to Devil Trigger (which I think is BS), and it's not that much easier with DMC4. And don't even get me started on the gimmicky Heaven or Hell and the masochistic Hell and Hell difficulty modes.
Zelda II is another one. I wouldn't have gotten through that game were it not for ZD's video guide thanks to stupid parts like Death Mountain & the Great Palace, where you don't even know where you're supposed to go on top of all the enemies piling on top of you. The only reason I'd say that it's the easiest of all the toughest games I've played through is because a lot of its difficulty comes through that kind of stuff as opposed to actual skill-based challenges (though there are plenty of those, as well), so once you know the way, all that's left is the obnoxious enemies. Can't say it wasn't fun to beat, though.
Of course, I can't leave out the Souls games. Those are old-school RPGs brought into modern day -- TOO old school, actually. They're fun, but goddamn it, are they absurdly cheap at times. I love when games aren't afraid to make the player step up in order to overcome what trials lay ahead of them, but I shouldn't die because of things I never could have possibly seen coming.