In pass 1, just explore all of the maze, and if you find the object in a particular location, remember it. You may need the entire maze map to be able to calculate the optimal path for pass 2.
What is the problem with the object? Do you not know how to detect the presence of the object? What are the specs for the object -- size, color, shape, IR/sound beacons, etc? Based on those specs, different sensors would be more or less appropriate. Bascially, your sensors need to do two things:
1) Detect blocked areas (walls)
2) Detect the object.
Doing 1) is simple with IR or ultrasound distance sensors, or if "walls" are really tape on the ground, IR line sensors.
Doing 2) may be simplest with a webcam and some image recognition software.