You can do Trio of 9999 from the time you pass Home in Bikanel Desert because you find a Level 4 Key Sphere there which can be used with an Underdog's Secret, which you get 99 of from Rin when you meet him on the airship.

After that, at the Calm Lands you can race chocobos at the temple for 30 Wings to Discovery, which can be mixed for Trio of 9999. At this point in the game there is plenty of possibilities.