Why stop at three dimensions?

Why not a maze in four dimensions?  Easy each room would have up to eight links to adjoining locations, the usual up, down, north, south, east, west plus dimension4+1 and dimension4-1.  This would result in approximately 340282366920938463463374607431770000000 location.  I am not sure why any one would want a universe this large as it would take 1545613388631689428159281492 lifetimes to visit them assuming you can visit 100 locations per second.

Distorting the Geometry

Rooms do not need to be cubical, or any regular shape.  The random number generated from the coordinates could easily be used to determine the shape of the room.  Potentially there could be millions of of shapes.  If differing room shapes are used it makes projections into adjoining locations considerably more difficult but not imposable.

Walls do not need to be flat they could be corridors, of varying length and shape.  Walls could have windows in them.  Escalators could be used for up and down links.

It would also be possible to flatten a three dimensional universe into two.  The up and down links could be flatten so that appear on the same level however the perspective of projections into adjoining rooms will be distorted.  Walking in a circle would not necessarily bring you back to your starting point but instead take you up or down a level, although you would appear to be on the same level!

Fixtures and Fittings

Anything you can design can be randomly placed by the locations random number.  Computer terminals, furniture, etc. can be randomly place within the room.  Transporters, as in Star Trek, would be fun, taking you to another fixed or even a random location.

Movable items

These are more problematical.  Not if the maze is running on a standalone system but if a multi-user system would require some sort of central storage to track moveable items.  Not difficult but will slow down the process of displaying the location.  There would also need to be some sort of backup storage.  It might make sense to preload remote data. (See Looking Ahead)