I was the one that posted about having 635mb "orphaned". My situation is different than yours in that the space is not showing as used on iCloud but it is showing as being used on both my iPhone and iPad. Basically, at 1 time the video was synced across my devices. It originated on the iPad, was sent to iCloud, and back down to the iPhone. I since deleted it, but the space is still being consumed on both devices (although freed up on iCloud).
Here was my original post. Maybe something I've tried will help you:
I have a situation with a video that I've deleted still taking up storage space on both my iPhone and iPad. The video is 635mb.
I did enable iCloud Photo Library (beta) about a month ago. Subsequently, I turned it off as I was noticing a large amount of storage being used on both devices (and quite honestly, I didn't see much benefit of the iCloud Photo Library as I rarely use my iPhone/iPad cameras).
However, in the time I had iCloud Photo Library active, I had taken and deleted a few videos, including this one 635mb video in question.
Now, even though I have erased every photo and every video from my iPhone, iPad, and even via the iCloud.com Photos app, my iPhone and iPad still report using 635mb. I have been sure to empty the recently deleted items. If you look at my iPhone and iPad Photos app, everything is completely empty. Yet under Settings -> General -> Usage -> Manage Storage (for device), both my iPhone and iPad report 635mb used.
I've tried turning the iCloud Photo Library option on and off several times. I have also gone into Settings -> General -> Usage -> Manage Storage (for iCloud) and disabled, re-enabled, and re-disabled. iCloud Photo Library.
Strangely, when I had activated the iCloud Photo Library yesterday, that "deleted" video actually reappeared in my recently deleted items folder. I emptied it. But again, cannot recover the used space (and even turning off/on iCloud Photo Library doesn't cause it to re-appear again).
Any ideas to reclaim that space? I only have a 16gb iPhone, so 635mb is pretty significant. I have not yet tried erasing the device and restoring from backup, but that might be an option.