Yea sadly its just not possible.
Well, actually it is possible but i doubt its the answer the OP is looking for.
Anytime you encode a video, or recode there is always a loss in quality. How much of a loss depends on the settings the original encoder used, and the quality of the source media.
Recoding a already compressed file make quality loss even more apparent. Then by upsizing the poor quality source, you'll in effect amplify the flaws even more.
The only way to really improve the quality is by having the original source. The better quality the source, the better the results.
A DVD source for example, can be upconverted from 720x480 --> 1280x720 and look somewhat decent. If the right settings are used and high enough of a bit rate (more than source)
But you must have the original Source to start with, and even then the results will not be that spectacular.
Zune encodes look good on a Zune, because of the smaller screen, but when you stretch it out on a larger screen it doesnt look very good.
They can only use like 1 ref. frame for example, rather than 3-4
