I'm trying to increase the resolution of images containing lots of rasterized circle and ellipse parts, is there any algorithm that kind of detects these and uses a mathematical model to rescale them? Currently to me hqx looks best, but it's not specifically designed for this I think.
Astronomers and especially planetary scientists working with images from spacecraft are always needing to fit circles and ellipses to pixelated images. It is routine to find edges and centers of circles to 1/10 pixel accuracy by skillful fitting to the jaggies. However, converting the image to a sharp-looking higher res one is not among the goals of scientists. But there's no reason the geometric models coming from an ellipse-fitting couldn't be used that way.
Unfortunately, I don't know of any software tool or body of source code that's easily made use of for what you want to do (assuming you're not a planetary scientist working on spacecraft images) Google for keywords like "subpixel limb fitting planet" One large piece of software used which iirc can do this is IRAF.
This paper (may cost $ to download) might be useful http://dl.acm.org/citation.cfm?id=1759470