Cryptographic Services automatically restart even when disabling the service

I have the same issue as this post although it seems that the behaviour is not the same in Windows Server 2016.

I have a failing Windows Update (0x80070643), presumably because it looks like it's trying to download the same KB (KB2267602) with different version IDs at the same time. My goal is to reset the Windows Update procedure, and found this post that describes the process. I went through it and arrived at the step of removing the contents of the catroot2 folder and noticed that it failed with an 'Access Denied' message. I tried deleting one file at the time and it said that "Cryptorgaphic Services are using the file". So I check the services and stop the service, try to delete the file and it gives me the same error. I look back at the services and it has restarted.

Troubleshooting so far:

• Set the service to disabled - still restarts and changes start-up back to "manual"
• Remove the recovery setting (previously was "restart service after crash"), still restarts
• Force stop through task manager - restarts anyway

What I've found is that the service remains "stopped" until the second I click on "delete" for any file under the catroot2 folder. It does not restart when I create or delete files directly under the C:\ or on the Desktop. Something is re-enabling the services so that it is never truly shut down.

Is there a way to truly force a stop of the Cryptographic Services?