I'd settle for a DVD remastering. I'm currently watching the 3rd season of DS9 on DVD, and I don't remember the image quality being quite that bad. The bitrate doesn't even break 5 megabits per episode most of the time, and for a dual-layer disc without supplementary materials, that's just wrong.
I suspect Paramount probably abandoned the upscaling approach because they knew fans would never stand for it. So I would suspect the only avenues left for them are digging up all the film elements they used and re-compositing everything for HD, or redoing the effects in CGI. Personally, I think they should avoid the last one, given the disappointing (IMHO) job CBS Digital did with TOS. There were so many opportunites they just missed.