For any scroll using character, stock up on scrolls of continual light, and conjure up about 2000 balls of light, storing them in your container. They have no weight, so you can carry as many as you like. (I also find it amusing when someone kills you and takes you container, then has to deal with 2000 balls of light). Then when you go exploring, start fishing out balls of light to drop. These have the added benefit of giving you an exact number sitting in the room:

{Exites: north east south west}
(4) A glowing ball of light is here.


That way, each time you enter a new room, you can label it with a number, and keep notes. EXAMPLE:

ROOM #1:
Upon entering the maze, I started in room #1.
East from room #1 is room #2
North from room #1 is room #30
West from room #1 is room #10
South from room #1 is room #24
(NOTE: Room #1 might be the first room upon entering the maze, but it is NOT an exit)

This is kind of a long process and requires many balls of light, but you're sure to map the whole place out, as long as the maze doesn't change while you're in mid-process. If I'm not mistaken, there are a few of those around (this is quite possibly an error, but seems to be the case from my experiences). This sort of mapping is also possible with other items like food from a pouch of nourishment, etc. However, unless you have a way of keeping a large store of items with low weight (i.e. pouch of nourishment, chest of inhebriation), you could really weigh yourself down carrying enough to map the whole maze.