Windows hat da seine eigene Philosophie, was die Wallpapers angeht.
Bisjetzt trat bei mir dein Problem mit PNGs unter Win XP nur einmal auf.
Allerdings war das Problem wieder behoben, als ich das Wallpaper erneut ausgewählt hatte.
Die älteren Windows Versionen (Win 9x, ME und 2k) unterstützen nicht mal jpeg oder png als Wallpaper. Sie wurden nur unterstützt, wenn Aktive Desktop aktiviert war.
Allerdings verursachte Aktive Desktop enorme CPU Auslastung und der Desktop baute sich nur sehr langsam auf.
Beim Aktive Desktop wurde der IE als "Wallpaper" geschaltet und die Bilder wurden dann über den IE angezeigt.
Ab Win XP unterstützte Windows erstmals die jpeg und png Formate als richtiges Wallpaper.

Vielleicht ist dein Problem eine Kinderkrankheit von Vista.
Ich würde dir, genauso, wie Vincent, raten, dein Wallpaper als BMP zu speichern und dies dann zu benutzen.