Player mapping as an assumption
it was assumed that all games would occur in the "Theatre of the Mind",
Partially correct. One of the things that has not translated well over time is a standard "table" assumption that goes back to the original game (a convention that Basic D&D a and AD&D sustained).
Part of the older ToTM includes a player mapping function
The players start with a blank sheet of graph paper before they "go underground" and one player volunteers to, or is tasked with, the sketching/tracking/mapping of the party's progress as the DM describes their environment. Obviously, this is put on pause when combat starts, but here is an example from Wilderness and Underworld Adventures (OD&D, Book III). (My B/X is elsewhere at the moment, but it has a similar example in it): (Below is excerpted from OD&D, Wilderness and Underworld Adventures, 1074, TSR, pages 12 - 13).
EXAMPLE OF THE REFEREE MODERATING A DUNGEON EXPEDITION:
The players, equipped and ready, are assumed to have located a set of stairs descending to the first level beneath the ground. The Referee's part will be indicated REF, that of the "Caller" for the players being shown as CAL.
REF: Steps down to the east.
CAL: We're going down.
REF: 10', 20', 30' — a 10' square landing — steps down to the north and curving down southeast.
CAL Take those to the southeast.
REF 10', and the steps curve more to the south; 20'. Steps end, and you are on a 10' wide passage which runs east, southeast, and west. There is a door to your left across the passage on a northwest wall.
CAL Listen at the door — three of us.
REF (After rolling three dice) You hear nothing. (At this time a check for wandering monsters is also made.)
CAL Ignore the door and proceed along the corridor southeastwards.
REF 10', 20', 30', 40', 50'. "Four way": Northwest, northeast, south and southwest — the south passage is 20' wide.
CAL Go south.
REF 10'-70': passage continues, doors east and west.
CAL Listen at the east door.
And so on. From an originally agreed orientation of "north" the mapping process goes on with the "mapper" paying attention to the Referee/DM and making a map. Mistakes were not that uncommon and it was assumed as a play style that this was OK.
I recommend that you try this with your group. They may find this change in challenge interesting.
How do the battle map and miniatures fit into this?
What we found worked best in our groups in OD&D, Basic, and in AD&D was that you don't put them into play until the situation calls for it. Everyone is supposed to pay attention to the map the mapper is sketching out. (Yes, put that cell phone down). The players can rotate mapping responsibility so that each gets a turn to try this out.
The REF/DM can always ask any of the PC's who are not mapping "what are you doing/paying attention to as the party progresses?" between encounters, particularly if the character has a skill or a reason to notice something the other players may not: dwarves have a skill that lets them sense sloping passageways, for example.
Bring out the map & figures for major areas and when combat comes
Switch from the generic marching order (see below) to setting up the figures in the room / cave / passageway / whatever, which is quickly sketched onto the battle map by the DM.
Either a detailed search (when discovereing a significant room/cave, etc) commences, or the NPC encounter / battle commences. Between times, the party places their miniatures into whatever marching order they are in, off of the battle map, in a generic hall / passage / room / cave to be ready for the next encounter.
How do I make this work, this "sense of direction change and getting lost?"
To fit the adventure's feel, use the mapping that was an assumed part of the play. Approach your players with "try it, you'll like it." And they might. Yes, this may alert them in a meta game sense, but I'd not worry about that. Play on. But for one reason or another, this may not fit your group.
If adopting that mapping function disruption with your players, then look at what this maze is supposed to be as a challenge: it is supposed to represent "getting lost in the labyrinth."
Once the party enter the labyrinth, revert to theater of the mind and set the figures / battlemap aside until a significant encounter crops up.
Ask your players "how to you intend to keep track of where you are going?" Let them know, by your narration, that they feel a little confused, and as they move through the labyrinth they get the nagging feeling that of deja vu, or "haven't we been here before?" whether they have or not.
The second time I ran Keep on the Borderlands, for teens and pre teens, that's what we did for the labyrinth. We put the party into a marching order, and then I described what they saw and relied on them to either keep track of the right and left turns, or do something else. As one of them had read the old legends of Thesus and the Minotaur, after the second turn he declared (he was playing a cleic) that he was keeping his hand on the right wall, and that they would make "all right turns."
Yes, it may have been a bit metagamey to switch the setting like that, so they were as players alert to "something is not quite right here" but that's fine. They still had to decide how they would deal with that.
The above was one way to mitigate the "we are lost in the maze" problem in terms of presentation, so they kept making right turns until the next encounter ... for that group, this went over well.
Whether or not your group will respond to this will depend on what they expect in terms of "control" of the flow of play.