I figured your WU tool deleted the SoftwareDistribution folder then let Windows create it after a reboot. I did this manually to no avail.
I decided to do a clean install of W8. After the initial install I downloaded and installed about 53 updates. All went well. After the install I used Disk Cleanup to get rid of them. Took forever to complete but there was no Windows Update Cleanup entry in Disk Cleanup.
I then found there were 6 more updates ready to be downloaded and installed. I installed them. When I went to clean them the Window Update entry had next to it 28.0 MB. Hmmmmm... At this point I uttered a few expletives thinking I was going to end up in my original situation. However, they cleaned perfectly. Funny thing is that these 6 updates were about 650 MB. Where 28.0 MB came from I have no idea. My previous install might have hiccuped at this point thus leaving the 28.0 MB entry. I installed about 11 more updates and everything went fine. Disk Cleanup shows no Windows Update Cleanup entries at all.
The thing I don't understand, and maybe you can provide an answer, is that all the updates are still in my SoftwareDistribution\Download folder. There is 1.1GB worth of updates which sounds about right based on the download amounts I saw. I thought Disk Cleanup would delete the folder and files. Evidently not. I read somewhere that they get totally deleted in 10 days presumably by a maintenance task. I'll have to see what happens.