@fonzer: Ah, didn't think of Echo Tower, now that you mentioned it, it's quite obvious to me, too. (EDIT: And that all for a glorified shining grenade.)
I will check underwater again for the monster lair. Thanks a lot, anyway.
Regarding the Legendary Gear, someone in the Kingdom of chapter 4 mentioned the need of the ability to teleport, so I guess it's connected to the Genie from the lamp (haven't encountered any evil genies yet, so mine only has his default escape spell).
@Firefly: I'm not sure if you have to not press anything. I did cycle through the options and after a few moments, the symbol appeared above the opponent, but I could still switch mine to the superior option.
For anyone interested, the prize is the Lucky Sword which (roughly) doubles the moeny from battles.