I wonder whether this is limited to photos in the profile album, or whatever it is called, these days.
EDIT: I'll add this suggestion that I've made before, since you're going to have a LOT of people wanting to delete photos, if this problem proves to be significant. Delegate someone to spend a few hours writing a routine that will replace a cached photo with an identically sized, all white (or black, blue, whatever), no metadata generated image. So, you don't have to rebuild your image caches in order to ensure that a photo is really gone (well, except for the fact that it once existed, as demonstrated by the working URL and white image).
I've read the excuse made in the past that aggressive, large, integrated image caches made actual photo deletion "not an option". As long as you can overwrite existing bits in place, this should solve that. (Although I don't know about all the tagging you've now since overlaid onto the images.)