Legend of Dragoon. Melbu. Freaking. Frahma.
This. A thousand times over. Hardest boss I can think of off the top of my head, harder even than the one in Borderlands.
Really? I didn't find the Borderlands boss to be very hard. All you have to do is hide behind one of the pillars and pop out and shoot it every once in a while. If you stand behind the right one then it can never hit you except by sending you flying back (and then you just run and hide behind the pillar again).
Sonic Unleashed's boss is pretty frustrating. Because of the way you have to keep switching between characters it just becomes a pain. Especially the parts where you are Sonic, running around on the Golem-thing and avoiding Dark Gaia's tentacle/vines.
EDIT: Oh and the Patriarch in Killing Floor. He's got a rocket launcher, a minigun, can turn invisible, incredibly powerful melee attacks, and can heal himself if he gets low on health. Sure he's easy if everyone on your team has grenade launchers and LAWs but otherwise he can really hard. Especially on larger maps (like Farm) where he spawns and you don't see him for five minutes until a rocket flies out of no where and he starts firing his minigun at you.