As a variant on the jigsaw puzzle, and the cut circle puzzle, here are a few more:
1) Buy one of those toy invisible ink pens, and draw a copy of the map with it. Turn it visible as the party explores the dungeon. You may need a (probably yellow) transparency if you want to keep the "invisible" ink invisible.
2) Get the map to the same square-size as the graph paper you use with a photocopier. (It may take some fiddling.) You may want to mirror the map with the phtocopier (if that's an available option). Cover the (mirrored) map with another sheet of graph paper. Lightly trace the areas of map you'll want to reveal as single units.
During play, put the cover sheet, tracing-side down, over the (unmirrored) map. You can draw the incorrect areas on the blank side. As the correct info is determined, you can cut out the traced area that matches.
If you want to be really fancy, you can use tape or semi-sticky glue to hold the tracing down.
3) If you have the time/resources, create an NWN map.
4) On the pre-assembled side, there's Dwarven Forge and WizKids 3D Dungeons as Lego replacements. And there are a number of preprinted Geomorphs, including Cardboard Heroes, and a few others.
5) Alternatively you can create your own custom geomorphs, by paying Kinkos to expand the supplied map to a 25mm scale or a plotter. This will cost more than geomorphs, but less than Dwarven Forge. If you can scan and expand the copy on your own computer, you'll save some significant money.