WallpaperForRoamingProfiles
How to make wallpaper work with a roaming profile in Windows XP:
First, the wallpaper must be in BMP format. Using another format causes Windows to create a temporary BMP version that it uses instead. Of course, it stores this somewhere it won't find it again later. So, you end up with no wallpaper.
Put the wallpaper in C:\Windows\Web\Wallpaper. All users should have read rights by default.
Use RegEdit to modify the settings for HKey Current User\Control Panel\Desktop\*Wallpaper to point to the correct BMP file (if they do not already).