It should be available in Disc 4. Make sure the other key items (Rat Tail, Une's Mirror, Doga's Artifact, and the Griffin's Heart) are in your Key Items inventory (anyway, I think you have to have them so Magic Fingertip crops up instead of these items), then keep going into the Auction House. When the Magical Fingertip comes up, refrain from bidding until the auctioneer says '...Any more?', then bid (This doesn't always guarantee you the item, so if you have money issue, sell some un-needed equipment and/or save beforehand). Then take to the guy in Dagguerro, and he'll trade you for the Excalibur.

Hope this helps.