Star Ocean 2, universe mode, powered up version of the final boss.
This assumes you don't
cheat and keep him locked down the entire fight with the Eternal Sphere/Angel Armbands.
I could barely beat him on the normal difficulty, with max stats and equipment.
EDIT: Heh, oh yeah, forgot about IWTBTG. The Guy took me 3 days to beat, and if the death count can be trusted, a little over 1000 deaths. (I don't trust it though; I think it took ~600 tries)
EDITEDIT: Velius (from FFT) should be mentioned. Again it assumes you don't cheat with something (in this case accumulate and yell), but the strategy guide that came with the game even stated it was the hardest battle in the game. Him and his minions can use 3 square radius attacks that hit for anywhere from 150-500 damage, and this is a point in the game where your highest health units don't often have more than 400.
Also, if we count rom hacks, this guy.
He has 100% evasion rate, so any attack that can miss, will. He's immune to every status effect, and damaging attacks that can't miss will only do 1 damage. He can insta-crystallize your characters, has 999 health, and can heal himself to full whenever he wants.
Possible? Maybe. Chances? The greatest computer in the world couldn't display that many 0's.