A. E. Jordan
I am in email catch up mode so others might have responded.
If someone went through the legal process of a name change they were required by the law to publish a notice. Most times they were done in the legal newspapers but they had to do it. If you get the name change file (if it still is available at the court) you will see they had to file a copy of the ad with the court to so it had been done.
As for the Health Department someone would have had to contact them with a copy of the name change paper work to get the birth certificate amended. Likely they needed it for something else all those years later and instead of showing the birth certificate as well as the name change documents they took the time to get the birth certificate reissued. I do not think the Health Department proactively took those steps, except in the case of adoption when they did change the birth certificate to hide the ID of the birth parents.