If so, what happens in that case? Can we also think about this with the quantum picture of light in mind? Is convex lens an example? Note: Not confined to euclidean space. Also, let's not talk about mirrors here. P.S.: I have an intuition for Fermat's principle (from Huygens' principle).
The best example is a lens focusing light. Every path through the lens takes the same time (but does not create different images). The center of the lens is thicker and the speed of light in glass is lower. This compensates for the longer path thought the edges of the lens where it is thinner. As a result, it takes light exactly the same time to pass through any part of the lens to get from an object to its image in the lens focus.
Yes. For a physical proof, consider mirages. Light from the sun "reflects" off the temperature gradient of the air near the ground, making it look like light is reflecting off the water. But light from the sun also goes straight into your eye. Both the straight-line path and the bent mirage path are extremal.
Yes, it can happen, and does happen in astronomy. What happens in this case is you see multiple images, one for each path. In the classic Einstein cross you're seeing four images of the same thing where the light followed four different locally optimal paths to get to us.