Having high HP is a double-edged sword. You don't want to give it more HP than you need to. If the battle is taking more than a half hour to finish even when you're playing right and at full strength, then you've given the enemy too much HP(see: Yiazmat). Nobody wants to sit there and slog through one battle for more than half an hour. It's just not fun, and the fun factor is just as important as the challenge factor. Give it enough HP to show you everything it's capable of doing, and forcing the player to set up counter measures to its attacks instead of shrugging them off as one-offs, but not so much that you're just sitting there doing the same cycle of strategies over and over for endless amounts of time.

A good way to make the battle last and keep the player's interest is making sure the battle changes as the enemy weakens. Increasing attack power and other stats is fine, but not very interesting by itself. Completely changing attack patterns is good. Changing forms is good(either as separate battles or as evolutions within the battle). Bringing in various types of re-enforcements is good. Having the enemy actually fall apart as you destroy parts of it is good.

Unique attacks are also a plus. Make it do something you've never seen before, something you didn't even think enemies could do. Stuff like locking abilities, destroying equipment(not permanently, please!), blowing away characters, new status ailments whatever. Anything to make the player stop and think about how to react. If you're just going to spam "Ultimate Attacks #24-56" without bringing anything new to the table, the player will get bored, even if the battle is technically challenging. Surprises are a major plus in specialty battles like super-bosses.

Also, luck should NOT be a major factor in any drawn out battle. If you're going to make a boss that takes some amount of luck to beat, you want the battle to be short and vicious, not long and drawn out. Ozma is a good example of a luck-based super-boss. He can end the battle in one move if he chooses, but he has very low HP. I can guarantee nobody would enjoy the Ozma fight if he had 600,000 HP instead of 60,000. Dying for no reason that you could possibly have prevented right at the end of a long fight is not fun, it's frustrating and sadistic. If the player dies, they should always feel like it was their fault, not the game taking a cheap shot.