Clamum was right about the IE wallpaper, but if you want the default windows wallpapers they are in My Documents\My Pictures or something like that.
I'm not sure anymore. I always move them when I reinstall windows.
I HIGHLY recommend that you make a Wallpapers folder in My Documents so you always know where they are at.
I did it a little more complicated. I have mine on a bulk storage drive and catergorized by the website I got them from. (ACDSee makes this really easy.)
Currently have around around 2,655. Its a good idea to have them in one convenient place. 😉
Also, back to your original point: If you "deleted" it by right-clicking and saving a new image as the desktop background, then the old image is truly gone.