Donncha, the "good news" is that I was able to reproduce the issue consistently on a production site. At the moment, there is no perturbation for our readers, and this causes only a mild annoyance to the editors. A few interesting things:
1/ Once WP Super Cache 1.0 is activated, we consistently bump into a problem if we try to delete an image from the media library (it would time out, basically).
2/ However, this happens ONLY if there are a relatively large number of files in the cache. If I delete the cache, I can delete media files again.
Now that an empty cache and a busy cache yield different outcomes, I may be able to reproduce this in a dev-environment. Looking at the log, I don't see anything that caught my eye (except this below), but I can send a 5MB log file over, if you're interested - contact me via Gmail or Facebook as we're connected on both.
It looks like the reason why I could not reproduce this on a test site was because the cache had not been used enough -- sneaky! Again, if I switch back to 0.999, this goes away for good, even with a cache directory that is well occupied.
Does this sound like a real issue to you?
/wp-admin/post.php?action=delete&post=33853&_wpnonce=90b0c355e3 rebuild_or_gc: rename to /PATH-TO-WWW/wp-content/cache/supercache/[DOMAIN]/[CATEGORYPREFIX]/[CATEGORYNAME]/index.html.needs-rebuild
/wp-admin/post.php?action=delete&post=33853&_wpnonce=90b0c355e3 gc: could not delete /PATH-TO-WWW/wp-content/cache/supercache/[DOMAIN]/[CATEGORYPREFIX]/[CATEGORYNAME] as it's not empty: index.html.needs-rebuild
Some stats, to give you an idea (not huge, right?):
wp-content/cache (245 files, 5.39MB)
wp-content/meta (248 files, 121KB)
wp-content/supercache (100+ 3MB)