There are 3 requirements you have to complete in order to obtain the Ultima Weapon.

1. Open the door to Eureka. You don't have to complete the dungeon though.
2. Complete "fixing broken pendant" quest from Princess Sara.
3. Complete "Something in the basement..." from Cid to obtain Orichalcum.
4. Getting Ultima Weapon from the Legendary Smith.

After you completed the Ancient's Maze, go straight inside the Crystal Tower. Inside, head straight into the north room, then examine the symbol on the wall to open a portal to Eureka. Finally, step onto the portal to exit Eureka, then leave Crystal Tower, and Ancient's Maze.

1. Board The Invincible.
2. Open your Inventory -> Formation -> then move Refia to the top.
3. Talk to the MogNet on the left.
4. Read all 5 letters from Takka (the letters appear one at a time):
   1. "Refia"
   2. "Kazus"
   3. "Must Be Getting Old"
   4. "The Legendary Smith"
   5. "Orichalcum"
5. Open your Inventory -> Formation -> then move Ingus to the top.
6. Talk to the MogNet again.
7. Read all 4 letters from princess Sara (again, they appear one at a time):
   1. "Hello, Ingus"
   2. "Bored..."
   3. "Sasune of Late"
   4. "Help!"

1. Go back to Floating Continent -> Castle Sasune (1), east tower, then talk to the princess at the top she'll hand you the broken pendant. You'll probably see the Legendary Smith standing outside princess Sara's room. You can either talk to her or ignore her completely is up to you.
2. Go to Kazus and talk to Takka (2).
3. Go back to the Surface World -> Northwestern Saronia (3), then find the Legendary Smith in the northeast corner of the woods.
4. Go back to Castle Sasune and give the pendant back to princess Sara.

1. Board The Invincible.
2. Go to Inventory -> Formation -> move Luneth back to the top.
3. Talk to MogNet and read letters from Cid until you see "Something in the Basement...".

1. Go to Canaan, Cid's house.
2. Talk to Cid (IMPORTANT).
3. Go down in to the basement, then kill the monster. You'll automatically obtain an Unknown Metal.
4. Talk to Cid again (IMPORTANT), he'll tell you that it's the rarest metal called Orichalcum.

1. Go to the Surface World -> Falgabard.
2. Talk to the Legendary Smith standing next to the weapon shop. She'll make the Ultima Weapon for you.