Thanks for the suggestion on the relation between sovle and eliminate. Another observation is that, for polynomial equations, solve seems to mess up only when the coefficients are not (real) rational:
work just fine, but
fail to find any solutions.
Ultimately, we should probably just look into the code of solve (which is indeed very long...) to track down the origin of the problem. But that's for another day ;-) (when I have some hours to kill)