What, everybody says Ultima weapon in FF8, what happened to Omega Weapon, I can kick Ultimecia's ass without using any other gf than Cereberus, and I can't last five seconds with that bastard.
But I believe that THE hardest boss I ever met was that secret boss from final fantasy in Super Mario RPG, you know the one with the four crystals... I catually finished the game, used my last available save, did some level up above what I was to beat the last boss, and still got my ass kicked.
Oh, and that whole level needed to beat a boss thing, well, I am pretty sure that when you observe the games of the old school, it was impossible to use this kind of algorythms, because the boss' stats had far less variables than the characters' and the proportionate evolution of a boss could not happen. If you lost, it might have been because you were not leveled up enough, but not because the boss was impossible... ... ... if you exclude the first encounter with bahamuth in FF3j, but that was because you had to run away... Anyway, the best example I can give is the 3 party battle in FF6 against Kefka, the first time I was beatten, without changing my teams, I just changed my strategy and I survived. With every boss, there are 2 ways to beat them, strategy or level uping.
But I can't think of a game making a boss impossible because the player was not leveled up enough, since games are made to be beatten.