I found the cause of my confusion with my question above. I will expand it in the following. I restrict the explanation to the Klein-Gordon (KG) equation. I will call the particles that follow the KG-equation mesons. For electrons/positrons following the Dirac equation it is about the same, except that the math is more involved.
If we search the solutions of the complex KG-equation $(\Box +m^2)\phi =0$. 2 solutions can be found:
$$\phi_+ = N e^{-i p x} \quad \text{and}\quad \phi_- =N e^{+ipx}$$
$N$ being some appropiate normalization factor. Whereas the first solution corresponds to $E=\sqrt{\mathbf{p}^2 +m^2}$ the second corresponds to $E=-\sqrt{\mathbf{p}^2 +m^2}$. (The dispersion relation of the KG-equation $p^2=m^2$ allows for 2 solutions.) Both solutions can be transformed in the corresponding other one by complex conjugation:
$$(\phi_+)^{\ast} = \phi_- \quad \text{and}\quad (\phi_-)^{\ast} = \phi_+\tag{0}$$
This behaviour is so important that it was coined with the name "charge-conjugation" and the negative energy solution is "associated with anti-particles". This operation apparently switches between particle and anti-particle solutions. (It has its equivalent if one thinks of the field operators:
$\Psi$ creates anti-particles, whereas $\Psi^\dagger$ creates particles if applied on the vacuum state.)
We are now going to find out what exactly "associated with anti-particles" really means. To this purpose we couple the mesons to the electromagnetic field. The corresponding equation is:
$$\left[-\left(i\partial^\mu -e A^\mu\right)(i\partial_\mu - e A_\mu) + m^2\right]\phi =0$$
or
$$(\Box +m^2)\phi = -ie\left(\partial_\mu(A^\mu \phi) + A^\mu \partial_\mu \phi \right)+ e^2 A_\mu A^\mu \phi $$
Actually, the equation for the anti-particle solution should be the same apart from the sign of the charge $e$:
$$(\Box +m^2)\phi = ie\left(\partial_\mu(A^\mu \phi) + A^\mu \partial_\mu \phi \right)+ e^2 A_\mu A^\mu \phi $$
So, the solution of this equation is very easy to find. It is just:
$$\phi_{anti} = \phi^\ast\tag{1}$$
So it is exactly as we expected. No surprise at all. But are we really sure ?
Let's check it out for a simple example case.
We are going to make a couple of simplifying assumptions. First the electromagnetic field is just a constant uniform electrostatic field: $A^\mu = (V,0,0,0)$. Secondly we only consider mesons in their rest system, i.e. their momentum is zero. Third we assume we can neglect terms $O(e^2)$. Then the last equation can be written like this:
$$(\Box +m^2)\phi = -2ie V \frac{\partial \phi}{\partial t}\quad\tag{2}$$
We can guess the solutions of this equation:
$$\phi_+ = N e^{-i(m+eV) t} \quad \text{and}\quad \phi_- = N e^{i(m-eV) t}$$
by plugging them into the equation above.
We want to know the anti-particle solution. We get it just by complex-conjugation:
$$(\phi_+)^\ast = N e^{i(m+eV) t}$$
As the negative energy solution is associated with anti-particles and the negative energy solution is obtained by complex-conjugation from the positive energy solution it should be like this, shouldn't it ?
But something is wrong with it. The (modulus of) energy of this anti-particle solution is the same for the meson as well as for the anti-meson. This is strange. It would neglect that the external field changed its polarity and this should be reflected in the energy.
We apparently overlooked that there is a second solution to equation (2) which is $\phi_- = e^{i(m-eV) t}$ and its complex-conjugation gives:
$$(\phi_-)^{\ast} = N e^{-i(m-eV)t}$$.
which shows indeed that the energy changes upon changing the polarity of the electrostatic field. So this one is the right one. This solution also has the nice property to propagate into the future. Therefore the conclusion is that we get the right anti-particle solution if we complex-conjugate the negative frequency/energy solution and not the positive frequency/energy solution. But actually, the latter choice seems so evident from equation (1). This was the cause of my confusion.
However, the now shown intimate relation between the negative frequency solution with the anti-particle solution via complex-conjugation can only well be seen when an external electromagnetic field is taken into the calculation. Otherwise one gets to curious results like (no external EM-field):
$$((\phi_+)^\ast)^\ast = (\phi_-)^\ast = \phi_+\tag{3}$$
where the $\phi_+$ on the lhs is a particle solution, whereas the $\phi_+$ on the rhs is an anti-particle solution. The first equality comes form (0) and the second equality from what we just have seen before. Well, (3) reflects that the fact that a particle and anti-particle should be completely identical if they are not exposed to an external EM-field. But -- this was another cause for my confusion -- the operation in (3) looks much more like a switch between particle and anti-particle, but is not how charge-conjugation actually is defined. But, a closer look shows that (3) is no longer valid as soon as an non-zero external EM-field is applied.