Check out SuperResolution from The Deemon, a new plug-in for Adobe After Effects 7 and Adobe Premiere Pro that uses super-resolution method to upsize video. It can be used to make HD videos from SD. The plug-in uses information from neighbor frames to upsize current frame. It accumulates information, so the more sequential frames are processed, the better quality you get. When it's first applied to a layer, it takes just a few frames preceding the current one.
It's Windows only and hopefully we'll have a demo up on our Free Demos page soon.