Thanks for all the tips. I've beaten the game once, and I'm going through trying to finish all 7 side missions.
I've completed The Heavens' Cavern, and The Hollow of the Earth-depths.
(3) Seabed Caves,
(1) Ice Cave.
However, I can't find the location of the final cave to get the Sapphire jewel.
Any help would be greatly appreciated.