I would check the Internet Explorer administration kit to see if there is a policy file for IE. That should give you all the options you need. If all else fails, you could write a custom adm file to use with the policy editor.
As a quick fix, you could specify a small image (company logo, or even just a screen color) to use as your wallpaper that gets copied down every time a user logs in. So even if they manage to set the wallpaper, next time they log in it would be gone.
Also, do you have a written policy (signed by employees) specifying that this kind of behavior is not allowed? I had some trouble with the forwarding of huge non-work-related files via email until I "reminded" all employees about our policy regarding the appropriate use of technology.