Then $\angle AEF = \angle AMF < \angle AMC = \angle ABC$, therefore the line $EF$ does meet the line $BC$ at a point $G$ such that $B$ is between $C$ and $G$. It is known that the circumcircles of triangles $ABC$, $AEF$, $EBG$ and $FCG$ have a common point, Miquel's point of the complete quadrilateral $BCFEAG$. The circumcircles of triangles $ABC$ and $AEF$ meet (again) at $M$, hence the quadrilaterals $MGBE$ and $MFCG$ are cyclic. It follows that:
$D \in BC \Leftrightarrow \angle MGE = \angle CGE \Leftrightarrow \angle AEM = 2\angle ABM = \angle AOM \Leftrightarrow O$ belongs to the circumcircle of triangle $AEF$.

The fact that the quadrilateral $MGBE$ is cyclic can be proven easily: $\angle EGB = \angle EBC - \angle BEG = \angle ABC - \angle AEF = \angle AMC - \angle AMF = \angle FMC$, hence $MFCG$ is cyclic.
Then, $\angle BMC = \angle BAC = \angle EAF = \angle EMF$, which leads to $\angle EGB = \angle BME$ and $\angle BME = \angle BGE$, which shows that the quadrilateral $GBEM$ is indeed cyclic.

Second solution. (given in the contest by Ioana Popescu)
* If $O$ lies on the circumcircle of $AEF$, then $\angle AEM = \angle AOM = 2 \cdot \angle ABM$, hence $\angle MEB = 180^\{\circ\} - 2 \cdot \angle ABM$, which shows that the triangle $MEB$ is isosceles. Similarly, triangle $MFC$ is also isosceles. Moreover, the two triangles are similar.
Notice that we have a spiral similarity centered at $M$. Consider the point $T$ such that triangles $MTD$ and $MEB$ are similar. Then $T$ belongs to the line $EF$ (because $EF$ is the perpendicular bisector of the line segment $DM$), so it follows that $D \in BC$. (For a spiral similarity, if one of the points glides on a line, like in this case $T$ glides on $EF$, then its image glides on the line "similar" to $EF$. In our case, $E \mapsto B$, $F \mapsto C$, $T \mapsto D$ and $T \in EF$, therefore $D \in BC$.)
* Assume that $D$ is on $BC$. Triangles $MEB$ and $MFC$ remain similar (AA) (be we no longer know that they are isosceles) and, again, a spiral similarity centered at $M$ takes $E \mapsto B$, $F \mapsto C$. There exists a point $T \in EF$ that is taken by the similarity into $D$. Triangles $MTD$ and $MEB$ are similar, but $EF$ is the perpendicular bisector of the line segment $MD$, hence triangle $MTD$ is isosceles. It follows that triangle $MEB$ is also isosceles, hence $\angle EMB = \angle EBM$, which leads to $\angle AEM = 2 \cdot \angle ABM$ and $\angle AEM = \angle AOM$. This shows that $O$ is on the circumcircle of triangle $AEF$.
Remark: The result remains valid in the case the circumcircles of triangles $AEF$ and $ABC$ are tangent, in which case we consider $M = A$. Indeed, the homothety centered at $A$ transforming the circumcircle of triangle $AEF$ into the circumcircle of triangle $ABC$ takes the line segment $EF$ into a parallel line segment, $BC$. Then $D \in BC$ if and only if $EF$ is a midline, which is equivalent to $AEOF$ being cyclic.