An endless dungeon with only a single sheet of graph paper

[nizrad]

So I have had this idea floating in my head for a while where I use a single 8.5"X11" sheet of graph paper to create an endlessly repeating semi-fractal like dungeon complex (my issue is personal satisfaction with the end results). The premise is to fill a sheet of graph paper with a Gygaxian/Arnesonian nightmare maze with an assortment of passages extending beyond the map (6,8,10,12, or even 20 work well), and a number of vertical access points in similar number. Number each point of egress to align with the appropriate die. For example there are 9 sets of stairs up and 9 down. 3 of these sets are spiral stairwells, 3 are standard single flight stairs and the last 3 are 20' wide. Players go beyond the border of the map/up or down some stairwell or shaft, roll the appropriate die, and the characters "reenter" the map at the resulting location. This can allow for large numbers of adventuring partird to explore the same location and wind up with drastically different maps.
For additional fun true north can be determined by a roll of a d4 whenever the characters go beyond the map or ascend/descend levels and then rotate the map as necessary (clockwise, counterclockwise what have you). Beyond this a handful of common dungeon features can be formulated for quick level based on-the-fly generation (such as pits with a depth of 10'/level with a variable chance for thing such as spikes, water, acid, monsters, additional secrets and so on). Cool looking rooms get to serve as multiple specials.
Designated routes can be planned to circumvent the endless and repeating nature of the dungeon overall, while additional designated routs might lead to fantastic treasures (both examples may defy the repeating nature of the dungeon as needed). Yet with the nature of a dungeon like this, mapping one's route of exploration becomes ever more important as it may prove to be the only sure fire way to escape back to the surface and safety. Additionally mapping the dungeon can create a form of fixed layout where as what has been mapped and explored does not change (do not roll for random stair and passage connections as usual).

I think the concept might work best with an unkeyed (or mostly unkeyed) map where the contents are generated on the fly and by the book (for the most part). 

Edited to make things more readable hopefully. Also expanded some ideas a bit. 

[Starbeard]

I think the last possibility is the best, the one where you use the template as a geomorph and whatever gets mapped becomes persistent for that dungeon.

Without the persistence, there is less incentive to map because of its inherent mutability. I can see a case where the players are encouraged to map because of foreknowledge that the dungeon in its entirety will eventually be mapped, requiring them to deduce true directions and where the randomized connecting points are, but for this to be achievable in a practical, actually sitting at the table sense I think the dungeon would have to be significantly smaller than a fully packed page, and there would have to be a regular series of incentives to reward progress in mapping it all out.

If I were to try it, I might use a full page but with maybe closer to the Holmes sample dungeon in density. Then I would gamify it by perhaps having a series of rooms where you could "throw a switch" so to speak, and through all the usual means the players could learn various combinations to reveal a hidden treasure somewhere. That way, repeatedly going back and working out the true nature of the map is always rewarding.