Well there was Final Fantasy 13. I made it to chapter 11, wherein the game supposedly gets good and...it didn't. Before that though, there were a few bosses (who according to FAQs were piss-easy) who I couldn't get past...despite having hit the level caps at the time.
GTA San Andreas. I almost quit playing that game because of the stupid, difficult, tedious, unskippable racing missions. I ended up quitting in the end though because of the stupid, difficult, tedious, unskippable flying missions. For fuck's sake game; I've been flying in-game for hours and had a high-level flight skill!