What's the state of the art in image upscaling?

Generally, fractal-based algorithms will turn up the best results. One example (which gets rave reviews, though I've not used it) is Perfect Resize. That said, as you mention, the data just isn't there -- especially by the time you account for (typically) the JPEG compression commonly found on web images. I think in a medium-sized image like the one you describe, you'll probably get decent results, but in smaller (such as thumbnail, or Flickr "small" size) images, nothing will get them to upscale to monitor size clearly.

I know this is question is pretty old, but I think Alien Skin Blow Up does a pretty impressive job. Here is your image scaled up 4x with it: http://www.picsarus.com/K7GUHI.jpg