Are you using just plain old sprite 1,x,y,image? Or are you pasting them down and copying and redrawing the the background manually using multiple screens?
Also when you reset all your images, sprites and variables are you using the same code as used at the start of the game? Or are you running more code to do it? If you are doubling your code, then try to get all your sprite setup and variable setup together(you probably have already), and put it just before your game start. Then just send it back to that code. All you need to add at the start of the setup code is if the sprites exist, delete them.
It may not help but it should eliminate the possiblity that you have missed something out in your exit game code.
Backdrop on could well sort it out if you have not set it at all.
Oh another thing, still see no need to delete the images, even if you are making sprites on the fly. I'm sure you can just load images back over the old ones if you want. The sprites maybe...
http://s6.bitefight.org/c.php?uid=103081