I just reproduced the problem by:
- Activating the Oxygen theme
- Uploading 2 images
- Activating the Confit theme
- Deleting the images
Several images remain (specifically in my case 110x70, 470x260, 650x380, 470x140).
So that's a third theme to add to your list. The odds are very small at this point.
I then switched to Tonic and did the same thing. Tonic creates images at 150xH, 300xH. Switching theme again, these are happily deleted by Twentythirteen, because Confit and Twentythirteen create images at the same sizes.
I tried several other themes (Vantage, Confit, Sixteen) and found that in most cases some images are not deleted.
tl;dr: In the sequence BeforeTheme > UploadImage > AfterTheme > DeleteImage, if the BeforeTheme and AfterTheme create images at the same sizes, then they will delete cleanly. If the BeforeTheme and AfterTheme create images at different sizes, then the deletion is only partial.
So it's not a theme issue at all (and I'm presuming that the "Delete Permanently" function is WordPress function). I agree with the bug report: WP should delete all sizes, no matter what theme is loaded.
Note that I'm not "someone who knows how the media library works under the covers", but I'm good at problem determination ... and in fact you don't need to know how it works to be able to confirm that it's not a theme issue, as the above analysis shows.
Thanks for asking!