Under what conditions do the phase margin and Nyquist criteria give the same results?
As you have pointed out, the nyquist stability criterion is more general, moreover, is the only stability criterion. Nevertheless, the Bode plot give us the exact same information that the nyquist plot does, so the stability of a system can be determined with either the bode or the nyquist plot, some times its easier with the former and other times with the latter. for minimum phase system this is usually easier with the bode plot, since you only have to see that (as you said) $$\angle L(j\omega) &gt; -\pi/2 $$
at all frequencies for which
$$|L(j\omega)| &gt; 1 $$

Answering your question explicitly, this is only valid for minimum phase systems. For systems that are not minimun phase the gain and phase margins are not as straightfoward to find.