We may assume that the parabola is defined by the equation $y = x^2$, while the circle is defined by the equation $(x-a)^2 + (y-b)^2 = R^2$. Let $A(a, b)$ be the center of the circle, $X_i(x_i, x_i^2)$, $i = 1, 2, 3, 4$, be common points of the circle and the parabola. Then $x_1, x_2, x_3, x_4$ are four roots of the equation
$$(x - a)^2 + (x^2 - b)^2 = R^2 \implies$$
$$x^4 - (2b - 1)x^2 - 2a x + (a^2 + b^2 - R^2) = 0.$$

It follows that $x_1 + x_2 + x_3 + x_4 = 0$ (Vieta's formula). Denote by $M(k, l)$, $N(m, n)$ the coordinates of the midpoints of the arcs $X_1X_2$, $X_3X_4$, respectively. Then, in particular, $\overrightarrow{X_1X_2} \perp \overrightarrow{AM}$, which gives
$$(x_1 - x_2)(k - a) + (x_1^2 - x_2^2)(l - b) = 0 \Rightarrow k - a = -(x_1 + x_2)(l - b).$$
Since $M$ belongs to the circle, we have $(k-a)^2 + (l-b)^2 = R^2$ hence
$$((x_1+x_2)^2+1)(l-b)^2 = R^2,$$
so $(l-b)^2 = R^2/((x_1+x_2)^2+1)$. Similarly,
$$(n-b)^2 = R^2/((x_3+x_4)^2+1).$$
Since $x_1 + x_2 = -(x_3+x_4)$, we get
$$(l - b)^2 = (n - b)^2. \tag{1}$$
It is not difficult to see that the slope of the line $MA$ is positive (because that of the line $X_1X_2$ is negative) hence $b > l$; similarly, $b > n$. Therefore from (1) it follows that $b - l = b - n$, or $l = n$, which yields $MN \perp Oy$ as required.