As noted, the state Dept. of Health has a position in this link on providing copies. They also have a page for genealogical interests, which says that
the New York State Department of Health provides uncertified copies of
the following types of records for genealogy research purposes:
Birth certificates - if on file for at least 75 years and the person
whose name is on the birth certificate is known to be deceased.
They also say that
The New York State Department of Health does not file records of
births and deaths that occurred in New York City and marriage licenses
that were obtained in New York City.
So the state is no help at all, except to say that you have to ask the city government. Their suggestion is this, which says that the Municipal Archive has birth records prior to 1910, but for years after that they refer you to the NYC Department of Health (that is a fairly useless general DOH link). However, a search there reveals this. Find the section that says:
I am an attorney retained by an entitled party and I need to order a
birth certificate for a client. How can I order a birth certificate?
That section says "Only entitled parties (defined below) and their attorneys may submit orders for NYC birth certificates". Below that it says for Birth Certificates
the entitled parties are limited to:
The person named on the certificate (the registrant)
Father (if named on the certificate)
That, BTW, means the person's parent, not your parent. They link to the application form which is here, which also says "Copy of a birth record can be issued only to persons to whom the record of birth relates, if of age, or to a parent or human service organizations" (again, parent of the person in question).
State law regarding vital records are in Article 41 of the Public Health Law: Title III is about birth certificates and Title VII is about vital records. The former is more about what facts are recorded on the official record. It does specify how to "get a new birth certificate", but that is not actually what you want (that is about changing the data officially on the record, e.g. changing a name or factual error). You presumably want a copy of a certificate (which is not a "new certificate"). If there literally is no such certificate (an unrecorded birth; record lost in a fire), the struggle to overcome that problem is huge. The latter title VII is about getting records. PBH 4173 says
1: Upon request, a certification of birth or of death or a certified
copy or certified transcript of a birth or death record shall be
issued by the registrar under regulations prescribed by the
2. A certified copy or certified transcript of a birth record shall be issued only upon order of a court of competent jurisdiction or upon a
specific request therefor by the person, if eighteen years of age or
more, or by a parent or other lawful representative of the person to
whom the record of birth relates.
This indicates that there is some path to getting a certified birth certificate, namely a court order (call a family law attorney). Moving on: PBH 4174 says that
1. The commissioner or any person authorized by him shall:
(a) upon request, issue to any applicant either a certified copy or a
certified transcript of the record of any death registered under the
provisions of this chapter ... (2) when a documented need to establish
a legal right or claim has been demonstrated...(6) upon specific
request of the spouse, children, siblings or parents of the deceased
or the lawful representative of such persons
Thus your parents (but not you) can, under NY state law, request a copy of the certificate. The point of divergence between the NYC representation of the case and state law is that NYC only mentions the person, mother, and father if named, but the state law allows a broader range of applicants. Although there is a state commissioner, PBH 4100(2)(i) states that "In the city of New York, the commissioner of the department of health for the city of New York shall implement the requirements of this paragraph". It is thus possible that there are city-specific regulations which more narrowly restrict access to vital records (I cannot find any such regulations, which does not mean they don't exist). Even if such restrictions are legally improper, if the NYC DOH position is that they will not issue a certificate to a person's child, it would require a lawsuit (hence attorney) to force them to change the policy.
If the original search was with the state of NY, theoretically a subsequent search with NYC DOH should reveal if there is a record.