Other answers have focused on the mechanisms of how to have a changing maze. I'm going to answer your other question: how many rooms you need so that there's less than a one in ten million chance a randomly generated maze repeats?
For the number of rooms you need, where people going through the maze do not enter the same room twice, you need a self-avoiding rook walk.
Here's an example for a 2x2 and 3x3 array of rooms. Think of the rooms as occurring at the intersections of the lines. The entrance is in one corner of the array, exit in the opposite corner.
So in the top row, in the 2x2, there's only 2 ways to get form start in one corner to finish in the other. In the 3x3 array of rooms, there's 12.
- In a 4x4 array: 184 possible paths.
- In a 5x5 array: 8,512 possible paths.
- In a 6x6 array: 1,262,816 possible paths.
- In a 7x7 array: 575,780,564 possible paths.
- In an 8x8 array, a chessboard: 789,360,053,252 (yes, over 789 billion possible routes).
You certainly don't need multiple floors, and you don't need to reuse rooms on a given single run through.
(Numbers from here)
Now, the thing is that the rooms certainly don't have to be identical, only that a given room is only connected to between 2 and 4 other rooms at most, depending on where it falls on the array network (and how many doors you allow to be open). So some might be small rooms, some long tunnels, whatever.
There is a downside to that: suppose the starting position is in the southwest corner. Someone entering your maze will know, if they've been through it before, there's only two possible rooms that come next, one to the north, or one to the east. If the path is to the north, they'll know that in the next room they can only go either north again or east. If enough groups make it through and compare maps they made, they could probably figure out the general concept of your maze.
However, that wouldn't necessarily do them any good. Look again at the possible paths through the 3x3 network. They might know there's only 9 rooms, but they wouldn't know which of the 12 possible routes they'll end up on. They might need to only go through 5 rooms. Or they might have to go through all 9 to reach the end.
For an 8x8 network of rooms, it would be a horror show. They start off, they don't know if they're going to be fighting traps and whatever in only 15 rooms, the minimum, or 64. With mapping, they might might have a good idea how many rooms they have left near the end of the run, but still...
And if you do only two floors, so two 8x8s on top of each other, with ladders connecting rooms so they might have to go up or down a level, and not knowing how many times...
So: an 8 x 8 network array of rooms, on each of two floors. Each room has between 2 and 4 doors, depending where it is in the network, and a trapdoor either on the ceiling or floor, depending what floor you are on, but only two doors/trapdoors can be opened: the one you use to enter the room, and the one you use to leave. Not only won't they know what you might have set up in a given room to deal with, they won't know if they'll only face 15 rooms (shortest route, single floor) or have to go through all 128 of them.
And to add even more fun, why assume they start and end on the corners? Consider the entrance to the maze itself consists of a long, winding tunnel which makes it difficult to determine how far they've traveled, when it suddenly comes an an abrupt end with a door. The only thing is, the end of the tunnel is moveable like an airport bridge, so when they open the door, they don't know what room on the west side of the maze they're entering. It might might be any one of the rooms on the west side.
And imagine that the exit consists of a long tunnel that wraps around the other three sides on both floors, that any given room on the north, east, or south sides might have the exit door. Now that screws up their mapping again because if they end up in one of those room, they don't know if the next door is the way out, or if they're going to be turned around and sent deeper into the network.
Another thing about thinking of it this way is that it doesn't have to be procedurally generated: for your 8x8 array of rooms, the computer can be programmed with all 789 billion possible routes; despite the number of routes, each can be coded easily, for example NNEESWSEENN... (describing what door in each room opens to the next). When a run is ready to go, the computer randomly selects one of the paths and it's ready to go and flagged so that it's not included in the next random selection.
This also allows you to set up "difficulty". Coded like I suggested, it's trivial to tell the computer "select one of the routes that has between 15 and 23 rooms" or "select one of the routes that's between 50 and 64 rooms", giving you difficulty levels through shorter or longer possible mazes.
By the time you get through 789 billion combinations, it's pretty safe to assume that someone who's been through once is never going to see the same route again, no matter how much of a human lifetime they keep running it.
Fun times, fun times.