I agree with most of what has already been posted. I'm proud to say that I killed most of the bosses in IWBTG, I want to say I killed all of them but it was a long time ago and when I think about it the rage takes over - I know I at least went most of the way though.
Super Meat Boy was quite frustrating as well. I haven't got 100% completion on that yet and I don't think I'll ever finish off the few dark world levels I have left, though I will give it a go when I get a controller as the keyboard controls I used to finish the 'normal' game aren't ideal.
I will say though, that even though it may not be considered hard in the normal sense, King's Quest II and that bastard bridge still haunts me.
Profanity: Dark Souls/Demon Souls aren't that hard at all. People just went bonkers over them because they're more challenging than your usual hard-mode run with 0 deaths these days.
They're pretty average difficulty games.
I can't really speak for Dark Souls as I'm yet to pick it up but Demon Souls I actually thought was quite tough to finish, at least without resorting to strategy guides. I went for the plat trophy and it felt really satisfying to do so, even if it was a bit of a grind.