Hmm... Hardest game I've beaten...
I beat Demon's Souls 2 weeks from buying it, and I rolled a thief and had like 20 points in luck by the end of it. It wasn't as hard as I was led to believe, but I did end up looking for a walkthrough or map for world 2-2, as I got lost in the tunnels way too much.
I beat Modern Warfare 2's campaign on Veteran, that took me a month.
I remember Yu-Gi-Oh: The Duelists of the Roses handing my ass to me when I was 10, but then after a couple of months I developed a deck that had monsters, easily summonable, that had 6000 attack points each. It was pretty easy from then on. I still hated the white rose campaign... God damn Yugi...
Also, Starcraft 2, and Red Alert 2's Allies campaign. Seriously, I hate some of these games, yet I know I'm going to buy Heart of the Swarm when it comes out! I hate blizzard, and I quit World of Warcraft, but seriously I don't know why I torture myself with Starcraft.
For tough games I haven't beaten yet, Final Fantasy VIII and Vagrant Story have annoyed me to no end! I also bought Crash Bandicoot from the once existant PSN store, having played it as a child and not having much trouble, only to realize I was one of the most persistent people to grace the earth when I was younger! I seriously don't know how I completed it.
Finally, the Thief series... I love the games, but I still haven't completed a single one, and I keep playing them near daily!