More realistic would be observing that the entry and exit are on the outer edge and the maze is simply connected, so a trivial left-hand rule [1] will solve the maze in linear time. On its own pretty boring. You could ad some randomness to make it interesting. But would it still have linear expected solving time if you do that?
[1]: https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_fo...
If you still want randomness, give the people a chance to follow the signpost or move randomly, but bias it towards following the signs the longer they've been in the maze.
This should scale pretty well, at the expensive of requiring a one-time recomputation whenever the maze is altered.
Instead of randomly picking from the 4 sides, pick one from the set of legal moves.
I appreciate that a "proper" pathfinding algorithm like A* would not be feasible given the number of guests but maybe taking into account what the guest sees ahead of them would already make it quite a bit more realistic?
You could weight the probabilities for each direction by the square root of the length of the path or something like that. And if you can see the exit set p=0, if you can see the exit set p=1.
I'm sure it would still be easy to fool though - just build very long indents and make sure the entry/exit are not visible until the last moment.