You've beened tainted by the Brady Games Guide. Burn it now.

Final Attack is actually found in the Battle Square. If you have won and learned Omnislash (51200 points after getting Tiny Bronco, 32000 after getting Highwind), won the W-Summon materia (64000 points), have the Ultima Weapon, and have 10 GP, the woman at the counter will ask if you want to participate in a special battle. Win that battle, and you'll get Final Attack.