Hi softwaremaniac,
I've had some time to look into this issue more. I would up having a second Server 2016 server that stopped updating. With my experience with the other machine I was able to determine the online image was corrupted and repair it using dism. Afterwards I ran sfc /scannow and it repaired, but unfortunately Windows Update still did not work. I also tried disabling Windows Defender and Give me updates for other Microsoft products on the original machine, but I didn't have any luck.
Both machines behave similarly (most of the time). The updates are downloaded and partially install. Then on a reboot the install continues until it reaches 99%. At that point it reverts back.
I know for future 2016 VMs I will be creating a new template to hopefully avoid any issues like this cropping up. In the meantime, if you have any more suggestions I am willing to keep trying them out.