how it is described when Beren finds his way through.  I think it is fair to say they are not just physical mazes, though, but mazes of enchantment. 

We encounter something similar around Rivendell; Gandalf has a heck of a time guiding Bilbo and the dwarves, and he knows the way, while Boromir almost doesn't make it at all.  Gandalf seems confident that no evil can enter Rivendell, yet no walls guard it.

Lothlorien is guarded by physical obstacles (a rushing river) and the tricks of the elves (they mislead the orcs by mocking their voices), but I am sure that if those devices failed Galadriel would have a few tricks up her sleeve.

Then look at what happens to Bilbo and the dwarves in The Hobbit.  First there is the enchanted stream, which sends anyone who touches it into a deep enchanted sleep.  When the dwarves look like they will avoid that trap, a white stag, which may well be magical, causes Bombur to fall into the stream.  When Bombur finally awakes he persuades the others to leave the path in search of food, but whenever they enter the elves' feast the elves disappear, and the last time Thorin, too, is put to sleep and captured.

So even without Melian's help the elves are capable of misleading those who wish to enter their lands.  I would guess that Melian's enchantments are a similar combination of natural barriers, tricks, and enchantments, which only someone as virtuous, strong, brave, fated, and lucky as Beren could avoid.

“I dislike Allegory - the conscious and intentional allegory - yet any attempt to explain the purport of myth or fairytale must use allegorical language.  (And, of course, the more 'life' a story has the more readily will it be susceptible of allegorical interpretations: while the better a deliberate allegory is made the more nearly will it be acceptable just as a story.)” (From Tolkien Letter # 131.)

Tips for posting in the Reading Room.