Well for starters, the game isn't older than the Internet. It's not even older than GameFAQs.
But anyway.
You can retry Yuffie as much as you want (though it takes a long time), and IIRC you can with Vincent too (you definitely can if you save/load spam).
The superbosses, I managed to beat Emerald without any help, though it took several tries. I just spammed quadra magic w-summon KoTR, and made sure I had Phoenix Final Attack. Which wouldn't be that hard to come up with. Ruby, Iunno. I guess some people were hust good with experimenting.
Final Heaven, I actually found on my own. I mean the game shoves that overworld theme down your throat so much that it was really pretty natural to try to play it on the piano if you did any goofing around on it at all. Probably helps that I'm a little bit of a musician.