If your going the do it yourself route, Chris is right photoshop is the answer.
A plug in like photozoom pro, will smooth the graduations and add fake detail, usually in the form of noise, which isn't "that" bad considering.
Another option is to make an image sequence in photoshop and build a script.
Convert the image in 16 bit lab color, overrezz it in steps to about 8k, then step it down to 2k, 12 bit srgb.
Sometimes and I mean sometimes, this will build a more natural noise like look, though detail will suffer, (detail will suffer no matter what) but hopefully rasterization will be less and banding will be less (especially if you have blues).
(This above process takes some experimentation, though remember looking at a single image for a motion segment is different than playing it. Playing it will sometimes correct for a lot of problems, sometimes it will make it worse and it will flicker. The other option is a company like And Transfer in Dallashttp://www.andtransfer.com/
I've worked with them before on "challanged" footage.
I had a client send some interview footage shot on mini dv from Jamaica that was shot in shadows and underexposed. By going to the older DiVinci 2k suite and doing a faux 4k transfer they could open up the faces in stepped graduations and color the rest of the scene and really made the footage go from a disaster to something more than useable.
And Transfer has a new 4k and an older 2k Di Vinci suite. The 2k takes the footage to 12 bit, in your case a faux 12 bit, but will allow opening of the shadows and some stepped uprezzing.
And Transfer use to be huge (before the recession) and had a 4 or 5 story building and an amazing colorists named Peggy that could do wonders with anything.
Now Brandon and Dylan are good and still have the legacy 2k DiVinci suite and the biggest crt monitor you've ever seen (I think it's 12 ft. wide, 16x9) which allows you to see graduations and tone like no lcd can.
I would give them a call first.
The third option is to start calling post houses in Hollywood, I would try Method and Sony, but there are many sources and the answer probably lies in a dedicated output/conforming suite that purposes for different media.http://www.sonypicturespost.com/digitalpicture/online.htmlhttp://www.methodstudios.com/
(btw: Germany also seems to be very good at post production services with less hassel than most).
Hollywood is the master of optimization and has been using legacy footage for years for the big screen. They know how to optimize for output better than anyone, that's why when you see a 2k movie on a huge screen like the cinerama dome it looks good, actually looks as good as 4k IMO.
Since so much work as moved to software only solutions and the one man band desktop, people think that a computer is a computer, 2k is just 2k etc. etc. and there is much more to motion imagery than file size.
The industry has changed with software only solutions and large houses like Asylum breaking up, it's now the wild west. It's a shame because a lot of the buying clients believe if you have the software and a desktop, you have a solution and there is a reason that post work takes a large team and dedicated artists that have decades of experience.
Do some homework on post production houses that optimize and I'll bet you find a decent solution. Also don't be afraid to negotiate a deal as some people look at "troubled" footage as a way to make a little extra profit.
Oh and one more tip. Not that the Creative Cow doesn't have good sources and people, but like all forums there are a lot of people with a lot of skill/budget levels. Look big first, like Hollywood and work your way down the list.
Sometimes the old ways, are the best, but Chris' idea is a good one. I am always amazed that when I talk to post effects artists that have (had) millions of dollars of software and hardware at their disposal how much real work for motion imagery is done in simple old photoshop and three upgrades ago after effects.
One more thing. Restoration is difficult no matter what the reason and the best way to make techically difficult footage work is to creatively design a new edit where the footage is moved around in a way that the issues and artifacts aren't really noticeable.
In other words I'd personally look for a creative solution before a technical only solution.
PS If your doing surround sound I'd really call Sony as sound is their specialty.
PS 2. I hope your client knows that any solution for any big screen regardless of original content, is expensive. It either takes specialized equipment or a lot of time and sweat equity.
PS 3. I'll bet at the end of the day, the real solution is to edit in your 720 source footage at 720 and call it a day. It's interesting that when I travel I see edits we've done on in-store monitors around the world.
We take great care in optimizing for clients "requirements" in specified output, but I routinely see a 2k edit on a 40 inch screen that the client has pulled down from the web. It's crazy to see rasterization, crushed colors, etc., but if you'll look around the store at the few people that are viewing it, it doesn't seem that they notice. They're just looking at the message.
I think we've all seen a new standard in quality as the world is accustomed to streaming video from you tube to netflix some of it good, some of it awful but they watch it, they enjoy it and don't seem too bothered.
I'm not suggesting that a bad output is the goal or shouldn't be given attention, but without a doubt there is a new standard.
PS 4 The one thing I've noticed about source material motion or still, is the better the capture, the better the look. A 60mpx digital back might seem like overkill for print or broadcast, but drop a downsized 2k still into an edit from a digital back and compare it to a downsized dslr shot and you'll see a huge difference. Same with the RED's vs. my 2k cameras. We have to dumb down the RED footage a little if it runs side by side a 4k capture even if the edit is 2k.
Sorry for such a long reply.