You probably have encountered that boss w/ ungodly aiming in an fps that snipes you miles away. How about a fighting game where the cpu always throws your ass around first and predicts every move you make? Or just a damn boss in an RPG that just won't die, and your strongest spells/physical do shit damage.
Let us begin w/ fighting games:
M. Bison, SF2. Holy shit, I spent a shit load of quarters trying to beat this bastard. He was ridiculously fast, strong, and when I tried to turtle it would toss my character around. Forget about jumping in. I think I beat him by spaming fireballs and welcomed him w/ dragon punches <_<
Omega Rugal, KoF: 95. Predicted your moves, would spam fireballs + reflects yours, jump in = genocide cutter. I hated this bastard, but eventually beat it.
For RPG bosses, the only one I remember beating once and only once was Ozma, from FFIX. It has this one move that basically one shoots your party (iirc). The only way I survived this was by using the DRG's jump ability to avoid it and revive the pt again. I'm sure it's easy, but never bothered to check a faq ;x
DMC3, this game was really hard. Every freaking boss was too strong, hell, even the normal mobs would put up a decent fight. I never beat this game, got too frustrating. Later on I got the SE and finally beat it.
MGF2G for the PSP. Most of the mobs are difficult, combo you, and will one shoot your slow character. I haven't thrown the PSP out of the window because of the wrist strap. This is the hardest fight: YouTube - HR9 Anger of Heaven and Earth. Pt. 1
Honourable mentions: Justice, GG series; Dural, VF; Heihachi, Tekken.
So what are yours?