File this under “silly bugs-by-design recognized by Microsoft but can’t do anything about but ruin a great user-experience” (see footnote), and also, “very useful Windows Vista tips from Long Zheng”. The latter being most important. This guide will show you the best way to stretch and apply wallpapers in Windows Vista whilst maintaining the best quality possible.
The problem
As many of you may have stumbled across this problem when trying to set your favorite Pokemon pictures as wallpapers, Windows Vista has a critical design flaw that prohibits wallpapers from being interpolated when stretched to the appropriate screen resolution. Take a look at this visual comparisons to see what I mean:

The jagged curved edge is caused by a lack of image interpolation. Without doing into too much detail, image interpolation is a mathematical method of upscaling images when the ratio is not dividable by 2. This is a problem because you are trying to scale for example 1 pixel into 1.3 pixels. Technically that is impossible, but with image interpolation, you could ‘mix’ pixels to create a perception of smooth gradual transitions between two pixels. Here is the above example in greater detail:

In Windows Vista, for some silly reason, the desktop control panel does not perform image interpolation correctly on JPEG images. Therefore, when you apply a wallpaper not exactly the same size as your screen resolution, the end result can be awful. But however, bitmap (BMP) images ARE properly interpolated from the control panel. Go figure that one.
The mind-blowingly simple solution

Quite simply, use the “Set as Desktop Background” function when you right-click images.
The “Set as Desktop Background” function utilizes the PIX engine, which powers the Windows Photo Gallery application. PIX supports image interpolation, and applies it correctly to images when you set as a wallpaper. As a side note: it’s unsure why the Windows Photo Gallery itself doesn’t use image interpolation on photos when zooming in pictures, but add that to the list of strange behaviors by-design at Microsoft.
An insider tell me this is a recognized problem even by the Microsoft designers themselves, but unable to fix because of the legal and legacy issues surrounding it. But at least you now know, the right and best way to apply desktop backgrounds in Windows Vista. But don’t tell your friends, let them suffer.
In addition: At least Vista maintains image aspect-ratio when rescaling to wallpapers, a concept XP never understood. So it’s not that much of a step backwards.
Update: Microsoft reads. Microsoft listens. Microsoft fixes. All in a day’s work.