I didn't think my technical suggestion was going to resolve the issue. I did want to confirm that Microsoft's fix didn't change those registry settings.
Based on the information in the article, Microsoft is clearly stating that issues with out of life-cycle products is not their problem and you must upgrade as seen in this part of the article:
"Customers who require additional support for Windows NT 4.0 SP6a must contact their Microsoft account team representative, their Technical Account Manager, or the appropriate Microsoft partner representative for custom support options. Customers without an Alliance, Premier, or Authorized Contract can contact their local Microsoft sales office."
Frankly, I think your only choice for resolution is to either:
Upgrade your servers to the latest Microsoft supported products.
Migrate from Microsoft OS to something else.
Roll-back that security update.
If any of the peers can recommend some other course of action, I'd like to be made aware of it for general knowledge purposes.
I am sure that my answer above isn't what you would like to tell your users and management, but the real truth is that no manufacturer of anything keeps making and supporting a product for 11 years. They are always rolling out a new and improved version be it cars, laundry detergent or toilet paper.
My advice, roll back the security update and then plan an upgrade or migration, whichever meets your needs best. Otherwise, you are going to face this issue over and over.