I uploaded a new picture to my album (which was empty). Then I soft-deleted the picture... the picture is gone, the album is empty again however the thumbnail of the soft-deleted picture is still being featured as the album cover.
Yes, the media cache, when it is rebuilt, only uses media that is "visible". So, ideally, when an item is deleted (or unapproved) the cache needs to be rebuilt. We've done that now, for the next release, thanks.
