Interpolation algorithms! Who would have thought there were so many? Nobody! Here is a list of them:

Software which does interpolation using sekrit proprietary algorithms includes Genuine Fractals, Photozoom (aka S-Spline), SAR (many algorithms!), Qimage (just uses Lanczos, i think), Smartscale.

Handy papers include 'Towards an overview of spatial up-conversion techniques' and 'Image resampling' (and its appendix A).

The Interpolate This boards are useful as a source of pointers to algorithms and software, if not expert knowledge.

The Richardson-Lucy algorithm for image reconstruction also sounds interesting; it's some kind of deconvolution. The Tschumperle-Deriche stuff mentioned above also has interesting noise-elimination applications. See also a dude's bookmarks.