I haven't tried Qimage or PhotoZoom (formerly S-splines), but I have tried Genuine Fractals. Don't expect miracles. It does arguably work up to 3 times linear scaling in some cases, or perhaps more regularly up to 2 times. If you push it too far you will get some very strange effects, but possibly no worse than most other interpolation tools.
Note: it's only worth using tools like this if you really need to enlarge, or print at very high resolution settings. At low resolutions, or on small prints, most pictures will be almost indistinguishable however interpolated.
I am sceptical of the incremental approach, but some have said it works for them. Some suggest that using Laczos interpolation works better, and there are others ...
One very promising form of interpolation is called "new edge interpolation" - see
http://neuron2.net/library/nedi.pdf for the article by Li and Orchard, and this page
http://chiranjivi.tripod.com/EDITut.html for some samples. In my opinion Li and Orchard's new edge interpolation gives the best results. However I don't know of any software which is readily available which does this yet.
You might find that Genuine Fractals gives better results on textured images, while new edge interpolation gives really good results where there are lines which can be inferred in the image. From what I've seen that is easily available, Genuine Fractals does give the best results - though I'd like to be able to get my hands on a new edge detection package.