The technique in this paper might be of use to you: http://research.micr.../kopf/pixelart/
Here's the comparison with hq4x: http://research.micr...rison_hq4x.html
However, it's pretty expensive...
I like the blur and threshold idea from Syranide; it would be very efficient. You could even apply an anti-aliasing filter such as FXAA before the upsampling step to get smoother results.
I actually thought about that specific microsoft article too, but I imagine that it would be too "jittery/quirky/erratic" for real-time use as even tiny variations could introduce major changes in the output I think (it is mind numbingly cool though!). If I'm not mistaken, I think they even mention that it has some issues with animations somewhere, but perhaps I'm mistaken.
This is not my area at all, but to me it seems like some kind of "blurring algorithm" needs to be used to keep it fluid and consistent between frames, anything that too intelligently decides "on individual pixels" seems like it would just cause erratic behavior in realtime.
Running FXAA before the upsampling actually seems like a really good idea I have to say, if it works well it would remove the "wobbly and jagged" look and could actually end up looking really good...
I was going to suggest some basic algorithm for just filling various edges and gaps with grey pixels as a way to smooth out the original image just to minimze the wobbly look, but it seems FXAA should just be better in every way.