What you're looking for is called Component Video Up-Conversion. Most manufacturers like Denon and Yamaha offer it on their higher-end models. What you want to remember however, is that the signal will still have the quality of the lower source. For example you will not see your VHS videos in progressive scan.

It is of course handy to have this feature when setting up the receiver with the on-screen display. It always drove me nuts on my old receiver to have to switch to a different source just to adjust the speakers.

Most online retailers now list Video Up-Conversion on the receiver's webpage of features, and most sales reps know what you are asking. If they don't, you're talking to the wrong sales rep.