Come to think of it, how would keeping deleted posts in the search results decrease necessity of refreshing search caches? Since our search result pages are in "latest at the top" order, every time a new post is given a certain tag, every page of the search results shifts down by one image, thereby fucking up all cached search results pages for that tag.
That's considerably worse than, say, a deleted post being removed from the n-th page of the results, which would only change the search results on pages beyond and including the n-th.
How about this: after a certain time period has elapsed, automatically purge deleted posts from the db, while keeping a list of MD5s of previously deleted posts, and only allowing priveleged users to upload files matching these MD5s.
Is this computationally more expensive than what we currently have?
Or if we want to be really hardcore, we can set up the search results in ascending order of date, but automatically starting at the last page. That way, whenever a new post was uploaded with a particular tag, it would only appear on the last page (incrementing the number of images on that page), or if the last page were full, would create a new page. This method would leave all the older pages intact.
Then again, people tag older posts quite often as well, which would disrupt older pages in the search results. This happens with the current method anyway, so I guess it's not a huge deal.
If we care about cache speed more than storage space, we could even store the most recent time that each tag was added to a particular image, and then display the search results for a given tag in ascending order of date of addition of THAT TAG to the image. Then we'd never disrupt the cached versions of older pages of the search results, though something would have to be worked out regarding how to handle multiple tag searches.
But of course this is all speculation. :)