Then why is a requirement set by Sakurai that characters must originate from video games?
You miss the point that Medusa from Kid Icarus is not the same as Medusa from Greek Mythology. She may be (and is) based on the mythological creature with snakes instead of hair. The team at Nintendo took that as a basis and created their own character out of that, who is now property of Nintendo.
Medusa from Greek mythology is NOT the Goddess of Darkness banished to the Underworld.
Medusa from Kid Icarus is NOT a gorgon nor slain by Perseus and neither is she the mother of Pegasus.
Okay, they have more in common like:
Original Medusa is the beautiful Goddess of wisdom and a particular rival to the Goddess of Wisdom Athene (who is the basis of Paluthena). Because Medusa didn't take the holiness of virginity sacred (she got preggers by Poseidon in the Temple of Athene) Athene cursed her and her sisters with ugliness beyond belief.
What I am trying to say:
Medusa is based on mythology but is still property of Nintendo.
Or else you could say: You can't put in Mario, cause there are real fat Italian plumbers in Brooklyn