I never got 9999 but I used 4x attack and did somehow got him doing 5000-5500 damage. It was mostly hasting like people sugested and my obsession with using him as often as I could. Also I used the Conformer+Morph with Yuffie in the sunken Submarine morphing EVERYTHING I SAW! Everything down there gave me Stat-up thingies and I focused on giving all the Power-ups to Vincent for the longest time so when I got his Weapon I was already doing alot. Probably a combination of the two, but if you want strength, those things can really help if you keep giving them to Vincent.