Fractal manipulation will give you the best quality, but there are not too many apps out there with fractal interpolation.
Try this:
Fractal
I remember long time ago there was a fractal plugin for Netscape that could zoom images many times without loosing much quality.
More image apps