When/why does the principle of least action plus boundary conditions not uniquely specify a path?

Multiple classical solutions to Euler-Lagrange equations with pertinent/well-posed boundary conditions (such solutions are sometimes called instantons) are a common phenomenon in physics, cf. e.g. this related Phys.SE post and links therein.

In optics, it is well-known that already e.g. two mirrors can create multiple classical paths.

Actually, the extra path is not irrelevant. If you put a light bulb at A and a $4\pi$ detector (this means $4\pi$ steradian coverage, i.e. it detects incoming light in any direction) at B, the detector will see light along both paths: direct, and bounced off the mirror, which is exactly the result you got from Fermat's Principle. If you want to exclude the direct path, you have to block it with an opaque wall.

The same thing goes for the elliptical mirror: the detector will see light coming in from every direction, which is again just what Fermat's Principle tells you: every path has stationary (i.e. zero first-order variation) travel time, and thus every path is a valid one for the light.

In Lagrangian mechanics, on the other hand, the state of the system contains both position and velocity - it's a state in phase space, not real space. You don't have to deal with reflections in phase space, and that usually rules out these cases where you have an infinite number of paths by which a particle could get from state A to state B.