[UtterParadox]

The first time I fought Velius, my turns went thus (after Wiegraf falls):

Turn 1: Ramza moves, hits with both swords (he has Double Weapon equipped and is a Knight).
Turn 2: One of my Ninjas moves in, attacks with boths swords, misses with one.
Turn 3: Ramza moves again for some reason, hits with both swords, Velius is slain.

Sheer luck. I've never beaten him so easily since.

Bosses I've found hard: The final boss from South Park (N64) is just plain cheap. If you hurt him, he recharges all his health back! Sure, you can stop it, but by the time the hit registers to stop it, he's fully healed.

Yaridovich from Super Mario RPG was a nightmare. Every one of his attacks knocks half your life off if you're not at ridiculously high levels.

Sephiroth, Kurt Zisa, and the Phantom from Kingdom Hearts are that game's WEAPONs, i.e., all optional bosses found only in America that cannot be stopped if you're under level 80. I learned this from personal, painful experience.

Marx in Kirby Superstar was trickier than any boss I had run into up to that point.

On one last note, the Beholder from D&D: Tower of Doom (an arcade game) made a career out of kicking my ass repeatedly.