I never really bothered with it, as when I first completed the game I had an Xplorer which gave me all Master Materias so I never needed to get KOTR, and later when I used an Xploder I also had 99 Desert Roses (and 99 Earth Harps - which was annoying, as I had to give all of them to the Kalm Traveller in order to give him a Desert Rose as well) so I always got a Gold Chocobo anyway.

I dunno if I'll ever do it, but I think all the Walkthroughs I own have guides for it, or at least most of them do.