Yes, that happens from time to time.
You have already cleaned up Windows Update, you have reset the Software Distribution folder. But yet your server still asks you to reboot every restart or worse, it does it for you without even prompting.
The fix is actually quite easy (if you hit the same issue as me)
Backup the following registry key, and then delete it. Reboot and you should be all good!