Just hit level 99 last night. And beat Sephiroth.
I kept going back to him from level 60 on every 5 level points or so.
Now that I know the secret I dont think you have to be level 99.
you need to have the Trinity Limit learned and a few Elixirs. That's all.
Second Chance and Once More are helpful as well, but not necessary.
After you get past the first reaction command, hit him with a trinity, then take an elixir and repeat until defeated.