Too long to comment:
A quick look around suggests that 'least median of squares' is the route to go, and the preeminent paper on it is by Roth and Levine [G. Roth and M.D. Levine. Extracting geometric primitives. CVGIP: Image Understanding, 58(1):1-22, 1993.]. Unfortunately, I could not find this article. A second reference (which I also could not find) might be [P. Rousseeuw and A. Leroy. Robust Regression and Outlier Detection. Wiley, 1987.]
I think this is the way to go because of a circuitous route. Firstly, page 22 of this presentation does it, and references this paper. This paper by Rosin about ellipse fitting and about the effect of outliers on least squares in particular mentions 'least median of squares' as a good alternative, and references both Roth and Levine, and Rousseeuw and Leroy as well. Unfortunately, Rosin's paper itself seems of limited use.
Other methods are mentioned in Rosin's paper as well. I hope this helps - good luck.