Equations of tangents are $y=m_1x+\frac{a}{m_1}$ and $y=m_2x+\frac{a}{m_2}$
I think this is correct.
and equations of normal to the parabola $x^2=4by$ is $y=m_1x-2bm_1-bm^3_1$ and $y=m_2x-2bm_2-bm^3_2$.
I don't think this is correct.
Let $(s,t)$ be a point on $x^2=4by$, i.e. $s^2=4bt$. Since $2x=4by'\Rightarrow y'=\frac{x}{2b}$, the equation of normal to the parabola at $(s,t)$ will be $y-t=-\frac{2b}{s}(x-s)\iff y=-\frac{2b}{s}x+2b+t$. Let $k=-\frac{2b}{s}$. Then, since $s=-\frac{2b}{k}$, the equation of the normal can be written as
$$y=kx+2b+\frac{s^2}{4b}=kx+2b+\frac{1}{4b}\left(-\frac{2b}{k}\right)^2=kx+2b+\frac{b}{k^2}.$$
So, in our case, we have
$$y=m_1x+2b+\frac{b}{m_1^2}\qquad\text{and}\qquad y=m_2x+2b+\frac{b}{m_2^2}.$$
Thus, since $y=m_1x+\frac{a}{m_1}$ and $y=m_1x+2b+\frac{b}{m_1^2}$ are the same lines,
$$\frac{a}{m_1}=2b+\frac{b}{m_1^2}\iff 2bm_1^2-am_1+b=0.$$
Now, the discriminant is positive, so $(-a)^2-4\cdot 2b\cdot b\gt 0$, i.e. $a^2\gt 8b^2$.
As harry pointed out in the comments, one has to consider the case where one of the tangents is the $y$-axis.
Two tangents drawn to the parabola $y^2=4ax$ from $(0,k)$ where $k\not=0$ are $x=0$ and $y=\frac akx+k$. It follows from $u^2=4bv,\frac ak=-\frac{2a}{u}$ and $k=2b+v$ that $bk^2-a^2k+2a^2b=0$. So, one has to have $a^2\geqslant 8b^2$. If $a^2=8b^2$, then two tangents drawn to the parabola $y^2=4ax$ from a point $(0,4b)$ are $x=0$ and $ax-4by+16b^2=0$ (at $(2a,8b)$) which are normals to the parabola $x^2=4by$ (at $(-a,2b)$).
In conclusion, the answer is $a^2\geqslant 8b^2$.
Let $(x_1,y_1)$ be the generic point of the locus.
It is well known that $$\frac {xx_1}{a^2}+\frac {yy_1}{b^2}=1$$ represents the line passing through the points of contact of the tangents from $(x_1,y_1)$.
Now consider the equation $$\frac {x^2}{a^2}+\frac {y^2}{b^2}-\left(\frac {xx_1}{a^2}+\frac {yy_1}{b^2}\right)^2=0$$ It is satisfied by the coordinates of the center and the points of contact.
Since it can be written $$x^2 \left(\frac {x_1^2}{a^4}-\frac 1{a^2}\right) + y^2 \left(\frac {y_1^2}{b^4}-\frac 1{b^2}\right) + \frac {2\,x\,y\,x_1y_1}{a^2b^2}=0$$
it is quadratic homogeneous so represents a pair of lines (degenerate conic)
, clearly the lines joining the points of contact to the centre.
It is not difficult to prove that the lines are mutually perpendicular iff the sum of the coefficients of $x^2$ and $y^2$ is zero, that is $$\frac {x_1^2}{a^4}+\frac {y_1^2}{b^4}=\frac 1{a^2}+\frac 1{b^2}$$
Best Answer
Note that the condition we have is not $m_1m_2=-1$.
Instead, since $y=\color{red}{m_1}x+\frac{a}{m_1}$ and $x=m_2y+\frac{b}{m_2}\iff y=\color{blue}{\frac{1}{m_2}}x-\frac{b}{m_2^2}$, we have $$\color{red}{m_1}\cdot\color{blue}{\frac{1}{m_2}}=-1\iff m_2=-m_1$$
Thus, $$\begin{align}\\&k=m_1h+\frac{a}{m_1},\qquad h=m_2k+\frac{b}{m_2}=-m_1k-\frac{b}{m_1}\\&\Rightarrow m_1k=m_1^2h+a,\qquad m_1h=-m_1^2k-b\\&\Rightarrow m_1^2h-m_1k+a=0,\qquad m_1^2k+m_1h+b=0\\&\Rightarrow m_1^2hk-m_1k^2+ak=0,\qquad m_1^2kh+m_1h^2+bh=0\\&\Rightarrow (m_1^2kh=)\ m_1k^2-ak=-m_1h^2-bh\\&\Rightarrow m_1=\frac{ak-bh}{k^2+h^2}\end{align}$$
Putting this into $k=m_1h+\frac{a}{m_1}$ gives $$\begin{align}\\&k=\frac{ak-bh}{k^2+h^2}h+\frac{a(k^2+h^2)}{ak-bh}\\&\Rightarrow k(k^2+h^2)(ak-bh)=h(ak-bh)^2+a(k^2+h^2)^2\\&\Rightarrow h(ak-bh)^2-(k^2+h^2)(ak^2-bhk-ak^2-ah^2)=0\\&\Rightarrow (ak-bh)^2+(k^2+h^2)(ah+bk)=0\\&\Rightarrow (ah+bk)(h^2+k^2)+(bh-ak)^2=0\end{align}$$