So, inspired by the discoveries on this thread, I set about creating an app to easily discover and delete space-wasting files. This app is now in Alpha stage, and will be advanced to Beta as soon as it is feature-complete.
Requirements: capability-unlock (interop-unlock plus EnableAllSideloading). In the case of files that can't be deleted normally, the app will attempt to use the Samsung-specific RPC Component to move them to the SD card (and delete them from there). The app will still run on non-Samsung phones, or those without SD cards (although you'll get a warning at launch in either case) provided they meet the other requirements, but some folders won't be cleanable.
Current state: Alpha 0.2.1
Alpha 0.2.1: Files will now be checked for the Read-Only flag, and it will be removed if possible, both before attempting an in-place deletion and after moving to SD. In case of an error, the exception type will now be given in the report. Files with a "Modified" date in the future will now be included by default as well.
Alpha 0.2.0: Added Move-to-SD-and-then-delete as a work-around to permissions issues. Added warnings if Samsung RPCComponent or SD card are not present. Truncated overly-long messageboxes to avoid the app hanging for a few minutes due to an accidental tap. Re-compiled as release build for performance.
Initial release (20 Feb 2014)
Source code is available at https://wp8storagecleanup.codeplex.com/
Please post feedback here!