I actually discovered this just the other day. The OP is right - Windows automatically compresses your wallpapers when you set them. At least it does when you use custom wallpapers - I'm not entirely sure how Microsoft does it for the default ones. It stores the compressed file in C:\Users\[username]\AppData\Roaming\Microsoft\Windows\Themes - you'll notice that "Transcoded wallpaper" is significantly smaller than whatever the actual image is.
Through some trial and error I've found a way around it though. Assuming your wallpaper is a .jpg, you first have to convert it to a .png (I use the Gimp or probably even Paint works). If it's a jpeg then Windows will always
compress it. How you need to set the background so that it's lossless seems to depend on your OS:
For Windows 8: Once it's a png you can just use File Explorer and right click -> set as desktop background. You can also use the Personalization menu from the desktop.
For Windows 7: The only way I could get it to not compress was to open the png in Firefox and right click -> set as desktop background. This works in 7 but creates artifacts in 8 - it's weird. I primarily use 8 so I haven't tested 7 as much.
The jpeg artifacts are particularly noticeable with vector art. I use this image is a test: http://fwallpapers.c...-background.png
You can see it for yourself - save it and set it via Windows Photo viewer - you'll notice the orangish curve in the middle has noticeable jpeg artifacting (even though the source is a png). Then try setting it via File Explorer (assuming Windows 8) - it's completely lossless. The artifacts usually aren't that noticeable - especially with nature photos and stuff; I'm just pedantic about my desktop backgrounds.
Edit: Huh, I thought using File Explorer caused compression for PNGs in Win8, but apparently it doesn't. I think it still does in Windows 7 though. The important part is converting it to PNG. Then just play around with different methods of setting it until the artifacts disappear.