Miotaurs eh....
Greetings,
Natural Cunning (Ex): Although minotaurs are not especially intelligent, they posses innate cunning and logical ability.This makes them immune to Maze spells, prevents them from ever becoming lost, and enables them to track enemies. Further they are never caught flat-footed.
---- Above from Monster Manual Page 137 Minotaur Entry copyright Wizards of the Coast
It does not say that minotaurs can intuit locations within a maze or any where, only that they cannot become lost. Your minotaur will still have to explore the maze he just will not be tricked in to wandering in circles. He has no ability to magically find the center and none to know the locations of anything else.
You can use all the normal tricks and plans to challenge them, only the eternally lost in the maze is out. Try using confined spaces to make the minotaur think and adapt his reactions. Encounters in tight spots can be a real challange for big characters, restrict swinging room, charging distance, head room, coridor width, or all or the above.