The mission "Freefall" (where you're supposed to jump out of your plane to take over another plane...somehow) in GTA-San Andreas. God, I hated that thing, took me almost as long to beat as the rest of the entire game.
The Dragon on the island (no idea what it's called) in Sacred. Nowhere to run from the fire. Thankfully he's optional.
"Steadwick's Fall" (where you're supposed to take the enemy's ridiculously heavy guarded capital within 2 or 3 months) in Heroes of Might and Magic 3. Took me some serious luck (the overpowered hero that's usually guarding the city you're supposed to capture just standing around next to a windmill and some wimp doing his job instead) the first time I beat it, and some serious abuse (getting tons of as high as possible leveled magic heroes in the level before and spamming around Implosions (strongest damage spell in the game, but still ineffective against high numbers) before eventually walking in with my army and cleaning up) the second time after losing my savefile for some reason I don't remember. I still haven't beaten the game by the way, been too busy playing random maps when playing it.
Leverkusen in Anstoß 3. No matter if its 2000 or 2030 and if my team consists of a bunch of incompetents or the world's best 11 players, I ALWAYS lose against Leverkusen, even when I keep reloading the game.
The Caliph in Stronghold Crusader. If I attack with a small army, they just get killed by his archers, no surprise. If I send a huge army, he'll just burn it to death. The only way to beat him seems either Maceman rushing (which I'll only to in 1v1 because otherwise my economy will be seriously crippled) or a long, long war of attrition where he'll finally die after centuries of bombing his castle with catapults (thankfully stone is an infinite resource in this game) and repeatedly destroying all exterior buildings.