Snake Charming
Using a Snake Charmer Flute on snakes in the area in front of Medusa's lair, they can be persuaded to search for Rare Serpent Eggs inside Serpent Nests. These eggs are the keys for the entrance to Medusa's lair. Four of them are needed.
Notes
Snake Charmer Flutes can be used while invisible, making the whole ordeal a lot less hazardous.