PhotoAcute does super-resolution very well: http://www.photoacute.com/

While not a PS plugin, Perfect Resize 7 Pro does shocking things. Our design team used it to resize images to the vertical size of a three story building and they still looked really good.

http://www.ononesoftware.com/products/perfect-resize/

S-spline

Genuine fractals (now called Perfect Resize)