Let $P$ be the midpoint of segment $ST$. Since $M\neq N$ the segment $ST$ isn't a diameter of circle $o$ centered at $O$, so there exists point $P$ such that lines $PS,PT$ are tangent to the circle $o$. By radical axis theorem lines $PS, PT, MN$ are concurrent. Hence $PS^2=PM\cdot PN$. Let $Q$ be the midpoint of segment $ST$. Then $Q\in PO$ and $PQ\cdot PO=PS^2=PM\cdot PN$ and we have concyclicity of points $M,N,Q,O$. Hence

An alternative proof for the second implication. Let $O_1$ and $O_2$ be the centres of the two circles and let $R_1$ and $R_2$ denote their radii. Let $R$ denote the radius of the circle centred at $O$. It's clear by homothety that we can redefine $O$ as the intersection of $SO_1$ and $TO_2$. We assume that $S, N, T$ are collinear and prove that $MO\perp MN$. Since $MN$ is the radical axis of the two circles, it follows that $O_1O_2\perp MN$, so it's enough to prove that $O_1O_2\parallel OM$. Notice that $OT=OS=R$, so $\angle OTS=\angle OST=\alpha$, while $\angle SOT=180^{\circ}-2\alpha$. Now since $O_1=O_1N=R_1$ and $O_2T=O_2N=R_2$, we obtain that $\angle O_1NS=\angle O_2NT=\alpha$, whereas $\angle TO_2N=\angle SO_1N=180-2\alpha$. Therefore $\angle NO_S=\angle TO_2N=180-2\alpha=\angle TOS$ so $NO_2\parallel SO$ and $NO_1\parallel TO$. Hence $NO_2OO_1$ is a parallelogram. Furthermore $NO_2=OO_1=R_2$ and $OO_2=NO_1=R_1$. But $O_1M=R_1$ and $O_2M=R_2$ so $O_2M=O_1O$ and $O_2O=O_1M$ which is enough to conclude that $O_1O_2OM$ is an isosceles trapezoid, giving that $O_1O_2\parallel MO$, as needed. Sadly, I don't think something similar can be done for the other implication. There's a reason why this was P3.