I have the following matrix $$M = \begin{pmatrix}0&a\\b&0\end{pmatrix},$$ where I assume that $a$ and $b$ can be complex. It has right-eigenvectors $$r_1 = \begin{pmatrix}\sqrt{\frac{a}{b}}\\1\end{pmatrix}$$ and $$r_2 = \begin{pmatrix}-\sqrt{\frac{a}{b}}\\1\end{pmatrix}$$ with eigenvalues $\pm\sqrt{ab}$.
Now, the left eigenvectors of $M$ should be the same as the right eigenvectors of $M^{\dagger}$ (hermitian conjugate), i.e. they are the eigenvectors of $$M^{\dagger} = \begin{pmatrix}0&b^*\\a^*&0\end{pmatrix},$$ which means that $$l_1 = \begin{pmatrix}\sqrt{\frac{b^*}{a^*}}\\1\end{pmatrix}$$ and $$l_2 = \begin{pmatrix}-\sqrt{\frac{b^*}{a^*}}\\1\end{pmatrix}.$$
But now I try to take the scalar product of e.g. $r_1$ and $l_2$, which clearly is not zero. I thought that a right eigenvector is orthogonal to all left eigenvectors (except for one). What am I missing?
You have $$ r_1^*l_2=\begin{bmatrix}\left(\sqrt{\frac ab}\right)^*& 1\end{bmatrix} \begin{bmatrix} -\sqrt{\frac{b^*}{a^*}}\\ 1\end{bmatrix}. $$ The problem you have is that you want to do arithmetic with square roots. And in reality the symbol $\sqrt{a/b}$ is not even well-defined. When dealing with positive real number, the convention is that $\sqrt r$ means the only positive square root of $r$. In the complex plane you don't have such canonical choice, so it is best to avoid square root symbols completely.
Rather, for your eigenvalues you will need the two roots $z_1,-z_1$ of $a/b$. When you calculate the left vectors, you will find yourself in need of the roots of $b^*/a^*$. Instead of choosing them randomly, as with $a/b$, you may now choose the roots to be $1/z_1^*$ and $-1/z_1^*$. Then the computation $r_1^*l_2=0$ becomes obvious: $$ r_1^*l_2=\begin{bmatrix}z_1^*& 1\end{bmatrix} \begin{bmatrix} -1/z_1^*\\ 1\end{bmatrix}=0. $$